SubArray

53 Maximum Subarray I

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

• DP

• dp[i]: in array[0-i], maximum subarray sum

def maxSubArray(self, nums: List[int]) -> int:
    # sum if current accumulate starting from possible counting poinnt
    ans = s = nums[0]
    
    for n in nums[1:]:
        if s < 0:
            s = 0
        s += n
        ans = max(ans, s)
        
    return ans

Maximum Subarray II

Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.

1. Traverse from left and record the minimum subarray at left[i]

2. Traverse from right and record the minimum subarray at right[i]

3. split at index i to find the maximum

public int maxTwoSubArrays(List<Integer> nums) {
    int[] left = new int[nums.size()];
    int[] right = new int[nums.size()];

    int sum = 0;
    int max = Integer.MIN_VALUE;
    // traverse from left
    for(int i=0; i<nums.size(); i++){
        if(sum < 0) sum = 0;
        sum += nums.get(i);
        max = Math.max(max, sum);
        left[i] = max;
    }
    sum = 0;
    max = Integer.MIN_VALUE;
    // traverse from right
    for(int i=nums.size()-1; i>=0; i--){
        if(sum < 0) sum = 0;
        sum += nums.get(i);
        max = Math.max(max, sum);
        right[i] = max;
        // System.out.println(max);
    }

    max = Integer.MIN_VALUE;
    for(int i=0; i<nums.size()-1; i++){
        sum = left[i] + right[i+1];
        max = Math.max(max, sum);
    } 

    return max;
}

Maximum Subarray III

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

• localMax[i][j]: the max sum must containing i in the j partition

• globalMax[i][j]: the max sum may not containing i in the j partition

• Func: local[i][j]=max(local[i-1][j], global[i-1][j-1])+nums[i-1], global[i][j]=max(local[i][j],global[i-1][j])

• Init: local[i-1][i] = global[i-1][i]=MIN, i=1-k

• Ans: global[len][k]

public int maxSubArray(int[] nums, int k) {

//    |-----\
//    |      \
//    |       \
//    |        |
//    |        |
//    |________|
//
    int len = nums.length;
    int[][] localMax = new int[len+1][k+1];
    int[][] globalMax = new int[len+1][k+1];

    for(int i=1; i<=k; i++){
        localMax[i-1][i] = Integer.MIN_VALUE;
        globalMax[i-1][i] = Integer.MIN_VALUE;
    }

    for(int i=1; i<=len; i++){
    // i must greater than k
        for(int j=1; j<=k && j<=i; j++){
            localMax[i][j]=Math.max(localMax[i-1][j],globalMax[i-1][j-1])+nums[i-1];
            globalMax[i][j]=Math.max(localMax[i][j], globalMax[i-1][j]);
        }
    }
    return globalMax[len][k];
}

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

public int minSubArray(List<Integer> nums) {
    int min = Integer.MAX_VALUE;
    int sum = 0;

    for(int num: nums){
        if(sum > 0) sum =0;
        sum+=num;
        min = Math.min(min, sum);
    }
    return min;
}

Maximum Subarray Difference

Given an array with integers.

Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

Return the largest difference.

1. Traverse from left, record the maxSubarray and minSubarray

2. Traverse from right, record the minSubarray and maxSubarray

3. diff = leftMax[i] - rightMin[i+1]

   public int maxDiffSubArrays(int[] nums) {
    int len = nums.length;
    int[] leftMax = new int[len];
    int[] leftMin = new int[len];
    int[] rightMax = new int[len];
    int[] rightMin = new int[len];
   
    int maxSum = 0;
    int minSum = 0;
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
   
    // traverse from left
    for(int i=0; i<len; i++){
        if(maxSum < 0) maxSum =0;
        maxSum+=nums[i];
        max = Math.max(max, maxSum);
        leftMax[i] = max;
   
        if(minSum > 0) minSum = 0;
        minSum+=nums[i];
        min = Math.min(min, minSum);
        leftMin[i] = min;
    }
   
    maxSum = 0;
    minSum = 0;
    max = Integer.MIN_VALUE;
    min = Integer.MAX_VALUE;
    // traverse from right
    for(int i=len-1; i>=0; i--){
        if(maxSum < 0) maxSum =0;
        maxSum+=nums[i];
        max = Math.max(max, maxSum);
        rightMax[i] = max;
   
        if(minSum > 0) minSum = 0;
        minSum+=nums[i];
        min = Math.min(min, minSum);
        rightMin[i] = min;
    }
   
    // calculate the max difference
    int maxDiff = Integer.MIN_VALUE;
    for(int i=0; i<len-1; i++){
        maxDiff = Math.max(maxDiff, Math.abs(leftMax[i]-rightMin[i+1]));
        maxDiff = Math.max(maxDiff, Math.abs(leftMin[i]-rightMax[i+1]));
    }
   
    return maxDiff;
   }

643 Maximum Average Subarray

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

• Use sliding window technique

public double findMaxAverage(int[] nums, int k) {
    if (nums.length < k) return 0;

    int max = Integer.MIN_VALUE;
    int sum =0;

    for(int i=0; i<k-1; i++){
        sum+=nums[i];
    }
    for(int i=k-1; i<nums.length; i++){
        sum += nums[i];
        max = Math.max(max, sum);
        sum -= nums[i-(k-1)];
    }

    return (double)max/k;
}

644 Maximum Average Subarray II

• Google

• Blog

• Binary Search