Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

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

 

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

 

Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

 class Solution {
    public int maxSubarraySumCircular(int[] A) {
       
        int sum = 0, maxSum = 0, diff = 0, minDiff = 0, totalSum = 0;
        maxSum = Arrays.stream(A).max().getAsInt(); //line 1
        minDiff = Arrays.stream(A).min().getAsInt(); //line 2
        for(int i=0;i<A.length;i++){
            totalSum += A[i];
            if(maxSum > 0){
            sum += A[i];
            sum = Math.max(sum, 0);
            maxSum = Math.max(sum, maxSum);
            }
            if(minDiff < 0){
                diff += A[i];
                diff = Math.min(diff, 0);
                minDiff = Math.min(diff, minDiff);
            }
        }
        System.out.println(maxSum+" "+minDiff+" "+totalSum);
        if(totalSum == minDiff)
            return maxSum;
        return Math.max(totalSum - minDiff, maxSum);
    }
}




Try it on Leetcode

Here the solution is based on Kadanae Algorithm. It is slightly modified.

a) maxSum intialisation indicates, if array contains only negative integers, then line 1 comment in above code is enough. No need to find maxSum for negative integers of array.

b) minDiff intialisation indicates, if array contains only positive integers, then line 2 comment in above code is enough. No need to find maxSum for negative integers of array.

If array contains both positive & negative numbers, then we need to find it during iteration.

1) Find maxSum, minDiff of array using Kadanae algorithm.

2) If conditions inside for loop fails, if & only if any one of steps (a), (b) are true.

3) During these iteration calculate totalSum also.

4) If totalSum == minDiff, then return maxSum.

5) Else Return maximum(totalSum - mindiff, maxSum)

Consider the below detailed explanation using above examples

 

EX 1:-
   A = [1, -2, 3, -2]
   maxSum = 3   (Maximum subarray sum from a given array)
   minDiff = -3  (Minimum subarray sum from a given array)
   totalSum = 0   (Total array sum)
   Maximum Sum = 3 (max)(Here totalSum is not equal to minDiff)
   So, we need to Return maximum(totalSum - mindiff, maxSum)

EX4:-
   A = [-2, -3, -1]
   maxSum = -1
   minDiff = -6
   totalSum = -6
   Here, totalSum == minDiff, thus return maxSum.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Share with your friends and help us to grow..

Happy Coding..!!