Word Break II (LeetCode Dynamic Programming)

Question: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Idea: Depth-first search with recursive dynamic programming. At each position of the input string s, break it to two halves, if the prefix is contained in the dict, recursively break the suffix to words. Use a hashmap to cache the broken strings computed before.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     HashMap<String,List<String>> map=new HashMap<String,List<String>>();  
     return dfs(s,dict,map);  
   }  
   public List<String> dfs(String s, Set<String> dict, HashMap<String,List<String>> map)  
   {  
     if(map.containsKey(s))  
       return map.get(s);  
     List<String> result=new ArrayList<String>();  
     int n=s.length();  
     if(n<=0)  
     {  
       map.put(s,result);  
       return result;  
     }  
     for(int i=1;i<=s.length();i++)  
     {  
       String prefix=s.substring(0,i);  
       if(dict.contains(prefix))  
       {  
         if(prefix.length()==s.length())  
           result.add(prefix);  
         else  
         {  
           String suffix=s.substring(i);  
           List<String> breakSuffix=dfs(suffix,dict,map);  
           for(String tmp:breakSuffix)  
             result.add(prefix+" "+tmp);  
         }  
       }  
     }  
     map.put(s,result);  
     return result;  
   }  
 }  

Word Break (Dynamic Programming)

Question: Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

Idea: Dynamic programming. Let dp[i] denotes from s[0]->s[i-1] can be partitioned, then dp[s.length()] is the result. For each position i, use all the words in the dict to "jump" where "jump" means if a word (assumes length x)contained in the dict matches a portion of the input string, set dp[i+x]=true. If we can finally reach the end of the input string, that means all the substrings along the way can be found in the dict.

Time: O(m*n) Space: O(m), where m is the length of the input string, n is the size of the dictionary.

Code:

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     int n=s.length();  
     boolean[] dp=new boolean[n+1];  
     dp[0]=true;  
     for(int i=0;i<n;i++)  
     {  
       if(dp[i]==false)  
         continue;  
       for(String word:dict)  
       {  
         int len=word.length();  
         int end=i+len;  
         if(end>s.length())  
           continue;  
         if(dp[end]==true)  
           continue;  
         if(s.substring(i,end).equals(word))  
           dp[end]=true;  
       }  
     }  
     return dp[n];  
   }  
 }  

Palindrome Partitioning II (LeetCode Dynamic Programming)

Question: Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Idea: Duo-Dynamic programming. Let P[i][j] stand for whether the substring between i and j is a palindrome. Then we just need to compare the two ends of i and j to derive the recursive function. P[i][j]==true if s[i]==s[j]&&P[i+1][j-1]==true or the substring has less than 2 characters (j-i<2). Then use another array variable D[] to cache the total number of partitions. In the worst case, each character of the input string will be split as a palindrome. Then if we found s[i->j] is a palindrome through P[i][j], we can fill the data into D. This can be done at the same time as calculating P[i][j] or in another individual loop.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int minCut(String s) {  
     int n=s.length();  
     int[] D=new int[n+1];  
     boolean[][] P=new boolean[n][n];  
     for(int i=0;i<=n;i++)  
       D[i]=n-i;  
     for(int i=n-1;i>=0;i--)  
     {  
       for(int j=i;j<n;j++)  
       {  
         if(s.charAt(i)==s.charAt(j)&&(j-i<2||P[i+1][j-1]))  
         {  
           P[i][j]=true;  
           D[i]=Math.min(D[i],D[j+1]+1);  
         }    
       }  
     }  
     return D[0]-1;  
   }  
 }  

Climbing Stairs (LeetCode Dynamic Programming)

Question: You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Idea: Dynamic programming. For each stage i, the person can arrive from stage i-1 and i-2. So dp[i]=dp[i-1]+dp[i-2]. We can set dp[0]=1 to simplify the code, or set dp[1]=1, dp[2]=2.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int climbStairs(int n) {  
     int[] dp=new int[n+1];  
     dp[0]=1;  
     dp[1]=1;  
     for(int i=2;i<=n;i++)  
       dp[i]=dp[i-1]+dp[i-2];  
     return dp[n];  
   }  
 }  

Unique Binary Search Trees (LeetCode Tree)

Question: Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

  1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Idea: Do not consider 1, 2, 3, 4 as numbers, just consider them as variables or algebraic symbols, e.g. v1<v2<v3<v4<v5.., vi, ..,vn. The values make no sense in this problem.

If we pick vi as the root, the left subtree is formed by v1->vi-1, the right subtree is formed by vi+1->vn. Since the left subtree and the right subtree are independent, the number of different trees rooted at vi is  numLeft*numRight, where numLeft is the number of subtrees formed by v1->vi-1 (i-1 symbols), the numRight is the number of subtrees formed by vi+1->vn (n-i-1 symbols).

So the algorithm is obvious: for each symbol vi, use it as the root, get the numLeft*numRight=num(i-1 symbols)*num(n-i-1 symbols). Accumulate the total number of all the roots v1->vn, we can have the final result.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int numTrees(int n) {  
     int[] dp=new int[n+1];  
     dp[0]=1;  
     dp[1]=1;  
     for(int i=2;i<=n;i++)  
     {  
       for(int j=0;j<i;j++)  
       {  
         dp[i]+=dp[j]*dp[i-j-1];  
       }  
     }  
     return dp[n];  
   }  
 }  

Interleaving String (LeetCode String)

Question: Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Idea: Dynamic programming. Let dp[i][j] denote whether s3[0...i+j-1] is a interleaving of s1[0...i-1] and s2[0...j-1]. Then we have the following recursion function:
dp[i][j]==true requires either
1) dp[i-1][j]==true && s1[i-1]==s3[j+i-1];
or 2) dp[i][j]==true && s2[i-1]==s3[i+j-1].
For the first row and first column, since the other string is empty, actually we are doing string.equals() one character by one character.

Time: O(n^2) Space: O(n^2)

Code: 

 public class Solution {  
   public boolean isInterleave(String s1, String s2, String s3) {  
     int m=s1.length();  
     int n=s2.length();  
     if(s3.length()!=m+n)  
       return false;  
     boolean[][] dp=new boolean[m+1][n+1];  
     dp[0][0]=true;  
     for(int i=0;i<m;i++)  
     {  
       if(s1.charAt(i)==s3.charAt(i))  
         dp[i+1][0]=true;  
       else  
         break;  
     }  
     for(int j=0;j<n;j++)  
     {  
       if(s2.charAt(j)==s3.charAt(j))  
         dp[0][j+1]=true;  
       else  
         break;  
     }  
     for(int i=1;i<=m;i++)  
     {  
       for(int j=1;j<=n;j++)  
       {  
         dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(j+i-1))  
         ||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Edit Distance (LeetCode String)

Question: Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

Idea: Dynamic programming. Let dp[i][j] stand for the edit distance between word1[0...i] and word2[0...j]. Then if word1[i]==word2[j], dp[i][j]=dp[i-1][j-1], since no need to change anything; if word1[i]!=word2[j], then dp[i][j] can has three sources: dp[i-1][j-1] (by replace), dp[i][j-1] by add one letter to word2[0...j-1], or dp[i-1][j] by add one letter to word1[0...i-1]. So dp[i][j]=1+minOfThree(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]).

Time: O(n^2) Space: O(n^2)

Code: 

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int m=word1.length();  
     int n=word2.length();  
     int[][] dp=new int[m+1][n+1];  
     for(int i=0;i<=m;i++)  
       dp[i][0]=i;  
     for(int j=0;j<=n;j++)  
       dp[0][j]=j;  
     for(int i=1;i<=m;i++)  
     {  
       for(int j=1;j<=n;j++)  
       {  
         if(word1.charAt(i-1)==word2.charAt(j-1))  
         {  
           dp[i][j]=dp[i-1][j-1];  
         }  
         else  
         {  
           dp[i][j]=1+minOfThree(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]);  
         }  
       }  
     }  
     return dp[m][n];  
   }  
   public int minOfThree(int a, int b, int c)  
   {  
     return Math.min(Math.min(a,b),c);  
   }  
 }  

Distinct Subsequences (LeetCode String)

Question: Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

Idea: Dynamic programming. Let dp[i][j] denote the number of distinct subsequence of S[0...i] and T[0...j]. If S[i]!=T[j], dp[i][j]=dp[i-1][j], since S[0...i-1] needs to contain T[0...j]; if S[i]==T[j], both two scenarios will be fine:
1) S[0...i-1] contains T[0...j]
2) S[0...j-1] contains T[0...j-1]
So dp[i][j]=dp[i-1][j]+dp[i-1][j-1].

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int numDistinct(String S, String T) {  
     int m=S.length();  
     int n=T.length();  
     int[][] dp=new int[m+1][n+1];  
     for(int i=0;i<m;i++)  
       dp[i][0]=1;  
     for(int i=1;i<=m;i++)  
     {  
       for(int j=1;j<=n;j++)  
       {  
         if(S.charAt(i-1)==T.charAt(j-1))  
           dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];  
         else  
           dp[i][j]+=dp[i-1][j];  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Decode Ways (LeetCode String)

Question: A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

Idea: Dynamic programming. We use dp[i] to denote the number of ways to decode the message before i (exclusive i). Then from i-1 and i-2, there are several possible scenarios:
1) from dp[i-1]: the digit must be among 1->9.
2) from dp[i-2]: the digit must be among 10->26.
So dp[i]= (letter[i] among 1->9)?dp[i-1]:0 + (letter[i] among 10->26)?dp[i-2]:0

Time: O(n) Space: O(n) (can be reduced to O(1) by reusing dp[i-2], dp[i-1], dp[i])

Easier to Understand Code:

 public class Solution {  
   public int numDecodings(String s) {  
     if(s.length()==0||(s.charAt(0)=='0'))  
       return 0;  
     int[] dp=new int[s.length()+1];  
     dp[0]=1;  
     dp[1]=(s.charAt(0)=='0')?0:1;  
     for(int i=2;i<=s.length();i++)  
     {  
       int lastTwoDigits=Integer.parseInt(s.substring(i-2,i));  
       dp[i]=((s.charAt(i-1)!='0')?dp[i-1]:0)+((lastTwoDigits>=10&&lastTwoDigits<=26)?dp[i-2]:0);  
     }  
     return dp[s.length()];  
   }  
 }  

Cleaner Code: 

 public class Solution {  
   public int numDecodings(String s) {  
     if(s.length()==0)  
       return 0;  
     int[] num=new int[s.length()+1];  
     num[0]=1;  
     num[1]=(s.charAt(0)=='0')?0:1;  
     for(int i=2;i<=s.length();i++)  
     {  
       if(s.charAt(i-1)!='0')  
         num[i]=num[i-1];  
       int lastTwoDigits=Integer.parseInt(s.substring(i-2,i));  
       if(lastTwoDigits>=10&&lastTwoDigits<=26)  
         num[i]+=num[i-2];  
     }  
     return num[s.length()];  
   }  
 }  

Dungeon Game (LeetCode Dynamic Programming)

Question: The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Idea: With a few simple equations, we can solve this problem easily. Let us use dp[i][j] to denote the minimum health needed to start from block (i,j) (including entering (i,j)) then go to (m-1, n-1), where m is the number of rows, n is the number of columns. We have the following equations:

(1) dp[i][j]>=1, since dp[i][j] can not be 0 or below anytime, even before entering any block.
(2) dp[i][j]+dungeon[i][j]>=1, since the knight's health should be at least 1 after entering the block[i][j].
(3) dp[i][j]+dungeon[i][j]>=dp[i+1][j], since the knight's health should be enough to start from the block under [i][j]
(4) dp[i][j]+dungeon[i][j]>=dp[i][j+1], since the knight's health should be enough to start from the next block on the right of [i][j].

In any case, equation (1) and equation (2) are required to be fulfilled. However, either (3) or (4) works, the knight can succeed. By moving the items on the left of equations (1) - (4) except dp[i][j] to the right, we have

(5) dp[i][j]>=1 
(6) dp[i][j]>=1- dungeon[i][j]
(7) dp[i][j]>= dp[i+1][j]-dungeon[i][j] OR dp[i][j+1]-dungeon[i][j].

Since we need to minimize the health needed, we take the minimum of the two routes in the equation (7). Then we have the final equation:
(8) dp[i][j]= maxOfThree(1, 1- dungeon[i][j], Math.min(dp[i+1][j]-dungeon[i][j], dp[i][j+1]-dungeon[i][j])).

For the dp blocks at dp[m-1][n-1], the last row and the last column, just remove the items out of the boundary.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int calculateMinimumHP(int[][] dungeon) {  
     if(dungeon.length==0||dungeon[0].length==0)  
       return 0;  
     int m=dungeon.length;  
     int n=dungeon[0].length;  
     int[][] dp=new int[m][n];  
     dp[m-1][n-1]=Math.max(1, 1- dungeon[m-1][n-1]);  
     for(int j=n-2;j>=0;j--)  
       dp[m-1][j]=maxOfThree(1, 1-dungeon[m-1][j],-dungeon[m-1][j]+dp[m-1][j+1]);  
     for(int i=m-2;i>=0;i--)  
       dp[i][n-1]=maxOfThree(1, 1-dungeon[i][n-1],-dungeon[i][n-1]+dp[i+1][n-1]);  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
       {       
         dp[i][j]=maxOfThree(1, 1-dungeon[i][j], Math.min(-dungeon[i][j]+dp[i+1][j], -dungeon[i][j]+dp[i][j+1]));  
       }  
        }  
        return dp[0][0];  
   }  
   public int maxOfThree(int a, int b, int c)  
   {  
     return Math.max(Math.max(a,b),c);  
   }  
 }  

Unique Paths II (LeetCode Array)

Question: Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.

Idea: Dynamic programming. The number of uniques paths from point (i,j) to (m-1, n-1) is path[i][j]= (obs[i][j]==1)? 0 : path[i+1][j]+path[i][j+1]. We can not go right (go down) from the last column (the last row). So the last column is path[i][n-1]=(obs[i][n-1]==1)? 0: path[i+1][n-1]. The same for last row.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
     if(obstacleGrid.length==0||obstacleGrid[0].length==0)  
       return 0;  
     int[][] obs=obstacleGrid;  
     int m=obs.length;  
     int n=obs[0].length;  
     int[][] path=new int[m][n];  
     path[m-1][n-1]=(obs[m-1][n-1]==1)?0:1;  
     for(int j=n-2;j>=0;j--)  
       path[m-1][j]=(obs[m-1][j]==1)?0:path[m-1][j+1];  
     for(int i=m-2;i>=0;i--)  
       path[i][n-1]=(obs[i][n-1]==1)?0:path[i+1][n-1];  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
       {  
         path[i][j]=(obs[i][j]==1)?0:path[i+1][j]+path[i][j+1];  
       }  
     }  
     return path[0][0];  
   }  
 }  

Unique Paths (LeetCode Array)

Question: A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Idea: Dynamic programming. Since the robot can only go right or down, path[i][j]=path[i+1][j]+path[i][j+1]. For the last column(the last row), the robot has no choice but go down (go right), so the path[i][n-1] = 1( path[m-1][j]=1 ). The result is path[0][0].

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int uniquePaths(int m, int n) {  
     if(m==0||n==0)  
       return 0;  
     int[][] path=new int[m][n];  
     for(int j=n-1;j>=0;j--)  
       path[m-1][j]=1;  
     for(int i=m-1;i>=0;i--)  
       path[i][n-1]=1;  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
         path[i][j]=path[i+1][j]+path[i][j+1];  
     }  
     return path[0][0];  
   }  
 }  

Triangle (LeetCode Array)

Question: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Idea: Dynamic programming. We have the distance from (i,j) to the bottom is dis(i,j)=Math.min(dis(i+1, j),dis(i+1, j+1))+valueAt(i, j). So we can fill the table from bottom to up, but adding an empty (all 0's) row at the bottom. Each row i has i+1 numbers. This algorithm will cost O(n^2) space.
However, we need an O(n) space algorithm. We can observe that to fill the block dis(i, j), we need the results from dis(i+1, j) and dis(i+1, j+1); to fill the block dis(i, j+1), we only need the result of dis(i+1, j+1) and dis(i+1, j+2), where dis(i+1,j) is no longer needed. So we can reuse the space at dis(i+1, j) by store the result of dis(i, j) at the same place of dis(i+1, j). Then we just need an one-dimension array to cache the results.

Time: O(n^2) Space: O(n)

Code:

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     if(triangle.size()==0)  
       return 0;  
     int n=triangle.size();  
     int[] dis=new int[n+1];  
     for(int i=n-1;i>=0;i--)  
       for(int j=0;j<i+1;j++)  
         dis[j]=Math.min(dis[j],dis[j+1])+triangle.get(i).get(j);  
     return dis[0];  
   }  
 }  

Minimum Path Sum (LeetCode Array)

Question: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Idea: Dynamic programming. Assume the F[i][j] is the minimum path sum from (i,j) to (m-1, n-1). Then we have the equation:
F[i][j]=grid[i][j]+Math.min(F[i+1][j], F[i][j+1]). The result is F[0][0].

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution{  
      public int minPathSum(int[][] grid) {  
           if(grid.length==0||grid[0].length==0)  
                return 0;  
           int[][] path=new int[grid.length][grid[0].length];  
           int m=grid.length;  
           int n=grid[0].length;  
           path[m-1][n-1]=grid[m-1][n-1];  
           for(int j=n-2;j>=0;j--)  
                path[m-1][j]=grid[m-1][j]+path[m-1][j+1];  
           for(int i=m-2;i>=0;i--)  
                path[i][n-1]=grid[i][n-1]+path[i+1][n-1];  
           for(int i=m-2;i>=0;i--)  
           {  
                for(int j=n-2;j>=0;j--)  
                {  
                     path[i][j]=grid[i][j]+Math.min(path[i+1][j],path[i][j+1]);  
                }  
           }  
           return path[0][0];  
   }  
 }  

Maximum Subarray (LeetCode Array)

Question: Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Idea: Dynamic programing. We can think this problem as dividing the whole array to many disjoint subarrays. Then the result is the maximum of the local sums of these subarrays. So we need to know how to divide the array, or in other words, to find where is the beginning of each disjoint subarray.

Assume F[i-1] is the sum of a subarray starting somewhere (can be anywhere) and ends at index i-1. Now we have array[i] at index i, shall we add i to the existing subarray or start new subarray from i? The answer is if F[i-1] drags down the value of F[i-1]+array[i], we start a new array, otherwise add i to the existing array. For example, array=[-1, 2], we need to start a new array from index 1, since the former sum F[0]=-1 will drags the next maximal sum F[1] down.
Therefore, we have the dynamic programming equation:
F[i]=max(F[i-1]+array[i], array[i]). And the result=max(F[0], F[1], F[2], ... , F[n-1]).

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public int maxSubArray(int[] A) {  
     if(A.length==1)  
       return A[0];  
     int preMax=A[0];  
     int maxSoFar=A[0];  
     for(int i=1;i<A.length;i++)  
     {  
       int maxHere=Math.max(preMax+A[i],A[i]);  
       maxSoFar=Math.max(maxSoFar,maxHere);  
       preMax=maxHere;  
     }  
     return maxSoFar;  
   }  
 }  

Maximum Product Subarray (HashMap Array)

Question: Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Idea: Dynamic Programming. We need to go through all the local maximals to get the global maximum (the result). Since the array may start with either positive and negative numbers, there are many cases of local maximals, e.g. previous maximal >0,  array[i]<0 or previous maximal <0, array[i]<0. It will be too complex to list all the cases.
However, the local maximal at position i must be among three numbers: previous maximal * array[i], previous minimal*array[i] and array[i] itself, e.g. [-1, 2] when i==1. So we just need to cache the previous maximal and previous minimal and use a function maxOfThree(a,b,c) to deliver the values to next calculation.

Time: O(n) Space: O(1)

Code:  

 public class Solution {  
   public int maxOfThree(int a,int b,int c)  
   {  
     return Math.max(a,Math.max(b,c));  
   }  
   public int minOfThree(int a,int b,int c)  
   {  
     return Math.min(a,Math.min(b,c));  
   }  
   public int maxProduct(int[] A) {  
     if(A.length==1)  
       return A[0];  
     int maxPre=A[0];  
     int minPre=A[0];  
     int maxSoFar=A[0];  
     for(int i=1;i<A.length;i++)  
     {  
       int maxHere=maxOfThree(maxPre*A[i],minPre*A[i],A[i]);  
       int minHere=minOfThree(maxPre*A[i],minPre*A[i],A[i]);  
       maxSoFar=Math.max(maxHere,maxSoFar);  
       maxPre=maxHere;  
       minPre=minHere;  
     }  
     return maxSoFar;  
   }  
 }  

Jump Game II (LeetCode Array)

Question:  Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Idea: I tried to write the code as self-explain as I could. Dynamic programming. The furthest position we can jump to from position i is F[i]=max(F[i-1], i+array[i]). Then we calculate the number of jumps during filling the table.

We scan the array from left to right, if we found the current index is smaller than the position the jumper has "arrived", we just calculate and cache the furthest position "canJumpTo" from position "arrived" or any position before "arrived". For example [5,3,1,1,4],  if the jumper arrived at index 2, the furthest position is max(5+0, 3+1)=5. If we found the current index is larger than "arrived", we jump once at the maximum distance. Once we reach the right boundary of the array, we stop the loop.

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public int jump(int[] A) {  
     int result=0;  
     int arrived=0;  
     int canJumpTo=0;  
     for(int i=0;i<A.length;i++)  
     {  
       if(i>arrived)  
       {  
         arrived=canJumpTo;  
         result++;  
       }  
       canJumpTo=Math.max(canJumpTo, i+A[i]);  
     }  
     return result;  
   }  
 }  

Best Time to Buy and Sell Stock III (LeetCode Array)

Question: Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Idea: Dynamic programming. Since at most 2 transactions are allowed, we can think it as at any time slot t , there is a buy/sell transaction pair on t's left side and a buy/sell pair on t's right.  By assuming each time slot as the middle point, get an array of the maximal profits. Then the maximum number of the sum of the left profit and the right profit will be the result.

Assuming the middle point is x, the left maximal profit leftMax(x) =Math.max(leftMax[x-1], prices[x]- the valley price appeared before). The right maximal profit rightMax(x)=Math.max(rightMax[x+1], the peak price appeared before - prices[x]).

Time: O(n) Space: O(n)

Code: 

 public class Solution {  
   public int maxProfit(int[] prices) {  
     if(prices==null||prices.length<2)  
       return 0;  
     int[] left=new int[prices.length];  
     int[] right=new int[prices.length];  
     for(int i=1,valley=prices[0];i<prices.length;i++)  
     {  
       left[i]=Math.max(left[i-1],prices[i]-valley);  
       valley=Math.min(valley,prices[i]);  
     }  
     for(int j=prices.length-2,peak=prices[prices.length-1];j>=0;j--)  
     {  
       right[j]=Math.max(right[j+1],peak-prices[j]);  
       peak=Math.max(peak,prices[j]);  
     }  
     int result=0;  
     for(int i=0;i<prices.length;i++)  
       result=Math.max(result,left[i]+right[i]);  
     return result;  
   }  
 }