Maximum Sum Circular Subarray

Posted: 19 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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 
Approach 1

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’.
Try Problem