Given a circular arrayC of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10
Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4
Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3
Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1
Solution: (Kadane algorithm)
Approach:
We find the max subarray sum
We find the sum of non-contributing element by inverting array and finding max sum.
Compare the sum obtained by both cases and return the maximum of the two sums.
classSolution{public:intkadane(vector<int> v) {int s =0;int maxS = INT_MIN;for (int i =0; i <v.size(); i++) { s = s +v[i];if (s > maxS) { maxS = s; }if (s <0) { s =0; } }return maxS; }intmaxSubarraySumCircular(vector<int> &A) {int maxSum =kadane(A);int sumArr =0;for (int i =0; i <A.size(); i++) { sumArr = sumArr +A[i];A[i] =A[i] *-1; }int minSum =-kadane(A);if(minSum == sumArr){return maxSum; }returnmax(maxSum, sumArr - minSum); }};