# 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;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/array/subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.