title: maximum subarray iii (from lintcode) dynamic programming solution
body: <p>Can anyone walk me through this solution below? What does p mean? why its range j-1 to i? Thanks
  Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.</p>
  
  <p>The number in each subarray should be contiguous.</p>
  
  <p>Return the largest sum.</p>
  
  <p>according to this blog(<a href="http://www.cnblogs.com/lishiblog/p/4183917.html" rel="nofollow">http://www.cnblogs.com/lishiblog/p/4183917.html</a>), the DP analysis is</p>
  
  <p>DP. d[i][j] means the maximum sum we can get by selecting j subarrays from the first i elements.</p>
  
  <p>d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}</p>
  
  <p>we iterate p from i-1 to j-1, so we can record the max subarray we get at current p, this value can be used to calculate the max subarray from p-1 to i when p becomes p-1.</p>
  
  <pre><code>public class Solution {
  /**
   * @param nums: A list of integers
   * @param k: An integer denote to find k non-overlapping subarrays
   * @return: An integer denote the sum of max k non-overlapping subarrays
   */
  public int maxSubArray(ArrayList&lt;Integer&gt; nums, int k) {
      if (nums.size()&lt;k) return 0;
      int len = nums.size();
      //d[i][j]: select j subarrays from the first i elements, the max sum we can get.
      int[][] d = new int[len+1][k+1];
      for (int i=0;i&lt;=len;i++) d[i][0] = 0;        
  
      for (int j=1;j&lt;=k;j++)
          for (int i=j;i&lt;=len;i++){
              d[i][j] = Integer.MIN_VALUE;
              //Initial value of endMax and max should be taken care very very carefully.
              int endMax = 0;
              int max = Integer.MIN_VALUE;                
              for (int p=i-1;p&gt;=j-1;p--){
                  endMax = Math.max(nums.get(p), endMax+nums.get(p));
                  max = Math.max(endMax,max);
                  if (d[i][j]&lt;d[p][j-1]+max)
                      d[i][j] = d[p][j-1]+max;                    
              }
          }
  
      return d[len][k];
  
  
  }
  </code></pre>
  
  <p>}</p>