LintCode 43: Maximum Subarray III (최대 와 그룹 을 얻 을 수 있 도록, 출력 최대 와)

public class MaxSubArray {

  public static int maxSubArray(int[] nums, int k) {
    //                 
    //                ，                  ，      
    //                 k ，  nums.length-1     k    
    //           Math.max
    //             ，  ，              ，       i nums      i 
    //   ，          ？               j，      i   ！
    //                        ？
    //                 i       
    //               i-1   （         ，    ）          
    //           ，             j    （        ）

    int len = nums.length;
    //              ，   ，    0
    if (len < k) {
      return 0;
    }

    // max[i][j]    nums    j           i  ，       
    int[][] realMax = new int[k + 1][len + 1];
    //         j ， j                ，           j       
    int[][] virtualMax = new int[k + 1][len + 1];
    for (int i = 1; i <= k; i++) {
      virtualMax[i][i - 1] = Integer.MIN_VALUE;
      for (int j = i; j <= len; j++) {
        //            j     （virtualMax                ），
        //           
        virtualMax[i][j] = Math.max(virtualMax[i][j - 1], realMax[i - 1][j - 1]) + nums[j - 1];
        // i j    virtualMax           
        //        ，realMax      j   
        realMax[i][j] = (i == j ? virtualMax[i][j] : Math.max(virtualMax[i][j], realMax[i][j - 1]));
      }
    }

    return realMax[k][len];
  }

}