code

Documentation

Overview

Maximum Contiguous Subarray(substring) -100, 1, 2 => 1, 2

Kadane Algorithm Dynamic Programming: O ( n )

Divide and Conquer method: O ( n lg n ) maximum of the following

getMCS(A, begin, mid)
getMCS(A, mid+1, end)
getMCS(crossing)

http://codercareer.blogspot.com/2013/02/no-44-maximal-stolen-values.html Problem: Maximize the money to rob without robbing adjacent houses.

Example 1. Rob 22(=15+7), not 11(=3+1+7)

Can't rob 3 + 15

___[ 3 ]___[ 15 ]___[ 1 ]___[ 4 ]___[ 7 ]___

Example 2. Rob 11(=3+1+7), not 9(=5+4)

___[ 3 ]___[ 5 ]___[ 1 ]___[ 4 ]___[ 7 ]___

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Longest Common Subsequence

Subsequence needs not be contiguous X = BDCABA Y = ABCBDAB => LCS is B C B

Dynamic Programming method : O ( m * n )