#LeetCode: Maximum Sum Circular Subarray

Also Check: Solutions Of May LeetCoding Challenge (2020)

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:
-30000 < = A[i] < = 30000
1 < = A.length < = 30000

Algorithm
We will declare 5 variables, sum (contains sum of all the elements), maxTillNow (max sum of elements till the current position), maxTotal(Max total of all the elements), minTillNow (min sum of elements till the current position), minTotal(min total of all the elements).

In each iteration we will perform below steps:
1). If the current element is less than summation of current element and maxTillNow, we will update maxTillNow as maxTillNow plus current element. Else maxTillNow will be set as  current element.
2). If the current element is greater than summation of current element and minTillNow, we will update minTillNow as minTillNow plus current element. Else minTillNow will be set as  current element.
4). maxTotal would be maximum of maxTotal or maxTillNow.
5).  minTotal would be maximum of minTotal or minTillNow.
6).sum will be set as summation of sum and current element.

After iteration, if all the elements are negative sum will be equal to minTotal, in this case maximum sum would be maxTotal.

Else, we need to subtract minTotal from sum and return it if its greater than maxTotal. Else we will return maxTotal.

GIT URL: Java Solution Of Leet Code's Maximum Sum Circular Subarray problem

Java Solution 1

Java Solution 2

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa.