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.
Traverse from left and record the minimum subarray at left[i]
Traverse from right and record the minimum subarray at right[i]
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
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.
Traverse from left, record the maxSubarray and minSubarray
Traverse from right, record the minSubarray and maxSubarray
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;
}