Max sub-array sum in a circular array

Lets first solve the problem for normal array-

Example —

Given array [4, 6, 7, -2, –3, –4, 20, -10]

Max Sum sub-array = (4+6+7–2–3–4+20) = 28

Solution —

Lets have currMaxSum & maxSum variables where currMaxSum will calculate max subarray including current element while maxSum will be sum in overall array

we have to iterate over each element & find the currMaxSum including current element & finally calculate the max sum by comparing currMaxSum and maxSum.

Code —

import java.util.*;
import java.lang.*;

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{

int arr[]= {4, 6, 7, -2, -3, -4, 20, -10};

int currMaxSum = Integer.MIN_VALUE, maxSum = Integer.MIN_VALUE;

for(int curr : arr){
currMaxSum = Math.max(currMaxSum + curr, curr);
maxSum = Math.max(maxSum, currMaxSum);
}

System.out.println(maxSum);
}
}

Output-

28

Circular array

Given array —[ 4, 6, 7, -2, –3, –4, 20]

Max Sum sub-array in circular array = 4+6+7 + 20 = 37

As per the example, first 3 elements & last element is forming the sub-array with max sum.

There can be two cases-

1. Subarray can be normal array with continuous elements
2. Subarray can include some last & first element

Case 1 : We have already solved max Sum subarray

Case 2 : As mentioned in the above example, it can include last & first elements. In this case, we can find the min sub-array & subtract it from total sub-array.

Example — [ 4, 6, 7, -2, –3, –4, 20]

min sum subarray = -2 -3 -4 = -9

total sum = 28

max subarray including last & first element = (total — minSumSubarray) = 28 +9 = 37

Final Conclusion — Answer will the max of the both the cases.

Better explanation — https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass