Last Updated: 19 Mar, 2021

Maximum Sum Circular Subarray

Moderate

Asked in companies

Solve now

Problem statement

You have been given a circular array/list ‘ARR’ containing ‘N’ integers. You have to find out the maximum possible sum of a non-empty subarray of ‘ARR’.

A circular array is an array/list in which the end of the array connects to the beginning of the array.

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

For Example:

The ‘ARR’ = [1, 2, -3, -4, 5], the subarray [5, 1, 2] has the maximum possible sum which is 8. This is possible as 5 is connected to 1 because ‘ARR’ is a circular array.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the ‘ARR’.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the ‘ARR’.

Output Format:

For each test case, print the maximum possible sum of a non-empty subarray of ‘ARR’.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea behind this approach is that the subarrays ‘ARR’ can be classified as one-interval subarrays or two-interval subarrays., So, if we can calculate the max sum in these two intervals, that will be our final result.

For example, if ‘ARR’ = [0, 1, 2, 3, 4, 5, 6], we could represent the subarray [2, 3, 4] as one interval [2, 4], but we would represent the subarray [5, 6, 0, 1] as two intervals [5, 6], [0, 1].

Using Kadane's algorithm, we know how to get maximum one-interval subarrays, so it only remains to consider two-interval subarrays.

To compute the two intervals, we calculate the maximum cumulative sum from each index's right and left.

Here is the complete Algorithm:

For computing the sum for a single interval we use kadane’s algorithm:

Initialize two variables ‘ANSWER’ = ‘ARR[0]’ and ‘CURRENT’ = ‘ARR[0]’.
Run a for loop from ‘i’ = 0 to ‘N’ and do the following:
- ‘CURRENT’ = ‘ARR[i]’ + max(‘CURRENT’, 0).
- ‘ANSWER’ = maximum of ‘ANSWER’ and ‘CURRENT’.

Let's say the intervals are [0, ‘i’], [‘j’, ‘N’ - 1]. Let's try to compute both intervals:

For computing the sum for [‘j’, ‘N-1’] interval do the following:
- Make an array/list ‘RIGHT_SUM’ of size ‘N’ and assign ‘RIGHT_SUM[N - 1]’ = ‘ARR[N - 1]’.
- Run a for loop from ‘i’ = ‘N’ - 2 to 0 and do the following:
  - ‘RIGHT_SUM[i]’ = ‘RIGHT_SUM[i + 1]’ + ‘ARR[i]’.
- Make an array/list ‘MAX_RIGHT’ of size ‘N’ and assign ‘MAX_RIGHT[N - 1]’ = ‘ARR[N - 1]’.
- Run a for loop from ‘i’ = ‘N’ - 2 to 0 and do the following:
  - ‘MAX_RIGHT[i]’ = maximum of ‘MAX_RIGHT[i + 1]’ and ‘RIGHT_SUM[i]’.
For computing the sum for [0, ‘i’] interval do the following:
- Make an array/list ‘LEFT_SUM’ of size ‘N’ and assign 'LEFT_SUM[0]’ = ‘ARR[0]’.
- Run a for loop from ‘i’ = 1 to ‘N’ and do the following:
  - ‘LEFT_SUM[i]’ = ‘LEFT_SUM[i - 1]’ + ‘ARR[i]’.
For computing the final result do the following:
- Run a for loop from ‘i’ = 0 to ‘N’ - 2 and do the following:
  - ‘ANSWER’ = maximum of ‘ANSWER’ and ‘LEFT_SUM[i]’ + ‘MAX_RIGHT[i+2]’.
- Finally, return ‘ANSWER’.

Solve now

02 Approach

We can optimize the previous approach because in this problem ‘ARR’ is a circular array. So there are the following two cases:

The first is that the subarray takes only a middle part, and we know this can be solved simply by using Kadane’s algorithm.
The second is that the subarray takes one part from the beginning of ‘ARR’ and the second part from the end of the ‘ARR’. Now we can transfer this case to the first one.
The maximum result equals the total sum minus the minimum subarray sum.

Here is the complete Algorithm:

Initialize variables ‘TOTAL_SUM’ = 0, ‘MAX_SUM’ and assign the minimum possible value to it and a variable ‘CURR’ = 0.
Run a for loop from ‘i’ = 0 to ‘N’ and do the following:
- ‘TOTAL_SUM’ = ‘TOTAL_SUM’ + ‘ARR[i]’.
- ‘CURR’ = ‘CURR’ + ‘ARR[i]’.
- If ‘CURR’ > ‘MAX_SUM’ then ‘MAX_SUM’ = ‘CURR’.
- If ‘CURR’ < 0 then ‘CURR’ = 0.
Initialize variables ‘MIN_SUM’ and assign the maximum possible value to it and update as ‘CURR’ = 0.
Run a for loop from ‘i’ = 0 to ‘N’ and do the following:
- ‘CURR’ = ‘CURR’ + ‘ARR[i]’.
- If ‘CURR’ < ‘MIN_SUM’ then ‘MIN_SUM’ = ‘CURR’.
- If ‘CURR’ > 0 then ‘CURR’ = 0.
Now check if ‘TOTAL_SUM’ = ‘MIN_SUM’ that means all the elements are negative so we return ‘MAX_SUM’.
Else return the maximum of ‘TOTAL_SUM’ - ‘MIN_SUM’ and ‘MAX_SUM’.

Solve now