> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/subarray.md).

# 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

```python
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

```java
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]

```java
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.

```java
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]

   ```java
   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

```java
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](http://www.cnblogs.com/grandyang/p/8021421.html)
* Binary Search&#x20;