Maximum Subarray IV

Problem:
Given an integer arrays, find a contiguous subarray which has the largest sum and length should be greater or equal to given length k.
Return the largest sum, return 0 if there are fewer than k elements in the array.

Analysis:
2/26/2018 update
这道题的坑真多。
1. corner case include when k > nums.length
2. sliding window problem, maxSum's inital value needs to be sum(0, k).
3. Maintain a minSum that k distance away from the current location.

Solution:

public class Solution {
    /**
     * @param nums: an array of integer
     * @param k: an integer
     * @return: the largest sum
     */
    public int maxSubarray4(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length == 0 || nums.length < k) {
            return 0;
        }
        int minSum = 0, sum = 0, min = 0, max = 0;
        for (int i = 0; i < k; i++) {
            max += nums[i];
        }
        sum = max;
        for (int i = k; i < nums.length; i++) {
            minSum += nums[i - k];
            sum += nums[i];
            min = Math.min(minSum, min);
            max = Math.max(max, sum - min);
        }
        return max;
    }
}

10/16/2017 更新
发现了一个空间复杂度更优的方法。不需要开一个sum[]数组来记录min prefixsum，直接用一个变量来保存min prefixsum。代码如下：

 public class Solution {  
   /*  
    * @param nums: an array of integer  
    * @param k: an integer  
    * @return: the largest sum  
    */  
    public int maxSubarray4(int[] nums, int k) {  
      // write your code here  
     if(nums.length == 0 || nums == null || nums.length < k) {  
       return 0;  
     }  
     int maxSum = 0, prevSum = 0;  
     for(int i = 0; i < k; i++) {  
       maxSum += nums[i];  
     }  
     int sum = maxSum;  
     int minSum = 0;  
     for(int i = k; i < nums.length; i++) {  
       sum += nums[i];  
       prevSum += nums[i-k];  
       minSum = Math.min(minSum, prevSum);  
       maxSum = Math.max(sum - minSum, maxSum);  
     }  
     return maxSum;  
   }  
 }  

为什么更新minsum放在了maxsum前面。因为prevSum的起始点是0, 第一次进入i = k这个循环的时候，是求index为0之前的prevSum。 这和maximum subarray更新minSum的情况不一样，maximum subarray是从0开始，也就是prefixsum[i]开始的，之前已经初始化了prefixsum[0] 的情况下的minSum，所以一进循环直接用minSum求得max之后再更新。
------------------------------------------------------------------------------------------
思路：
这道题做了，才是把prefixsum所有细节都搞懂了。

规定了k，就是把minprefix的范围给限制了。普通的maximum subarray，min prefix sum范围是0~ (i-1)。这道题的范围是0~(i-k)。类似于two pointer, 第一个指针是从0开始走到k-1后第二个指针才从k-1开始。

之前一直没搞清楚为什么min prefixsum的初始值是0。因为prefixsum[0] == 0, 那么前1个数的min prefixsum肯定是0。

实现:
因为min prefixsum和prefixsum不同步了，所以要把prefixsum存在数组里面。当i >=k （i是sum 数组index）的时候，才更新min prefixsum。这样就可以直接取满足条件的
prefixsum( sum[i-k+1] )和min比较。 为什么是i-k+1, i-k+1其实是越界了，因为这是才下一次循环准备的，下一次循环i++,  刚好在边界。当前循环更新min prefixsum是inclusive。maximum subarray求minSum的时候就是和current sum比较。

代码如下：

 public class Solution {  
   /*  
    * @param nums: an array of integer  
    * @param k: an integer  
    * @return: the largest sum  
    */  
    public int maxSubarray4(int[] nums, int k) {  
      // write your code here  
     if(nums.length == 0 || nums == null || nums.length < k) {  
       return 0;  
     }  
     int maxSum = 0;  
     for(int i = 0; i < k; i++) {  
       maxSum += nums[i];  
     }  
     int[] sum = new int[nums.length+1];  
     sum[0] = 0;  
     int minSum = 0;  
     for(int i = 1; i <= nums.length; i++) {  
       sum[i] = sum[i-1] + nums[i-1];  
       if(i >= k) {  
         maxSum = Math.max(sum[i] - minSum, maxSum);  
         minSum = Math.min(minSum, sum[i-k+1]);  
       }  
     }  
     return maxSum;  
   }  
 }