Maximum Subarray Sum - Kadane's Algorithm & 918. Maximum Sum Circular Subarray

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. 

class Solution {

public int maxSubArray(int[] nums) {

int n = nums.length;

int maxEnding = nums[0];

int res = nums[0];

for(int i = 1;i<n;i++){

maxEnding = Math.max(maxEnding + nums[i],nums[i]);

res = Math.max(res,maxEnding);

}

return res;

}

}

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:

Input: nums = [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10. 

 

 

class Solution {

public int maxSubarraySumCircular(int[] nums) {

int curMax = 0;

int curMin = 0;

int maxSum = nums[0];

int minSum = nums[0];

int tot = 0;

for(int num : nums){

curMax = Math.max(curMax,0) + num;

maxSum = Math.max(maxSum,curMax);

curMin = Math.min(curMin,0) + num;

minSum = Math.min(minSum,curMin);

tot += num;

}

if(tot == minSum){

return maxSum;

}

return Math.max(maxSum,tot - minSum);

}

}