Maximum Sum Circular Subarray

Moderate
0/80
Average time to solve is 10m
18 upvotes
Asked in companies
UberInfosysFlipkart

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
-2 -3 -1
4
1 2 3 4
Sample Output 1:
-1
10
Explanation Of Sample Input 1:
For the first test case:
The sub-array [-1] in the given ‘ARR’ has the maximum sum which is -1.

For the second test case:
The sub-array [1, 2, 3, 4] in the given ‘ARR’ has the maximum sum which is 10.
Sample Input 2:
2
4
3 1 -2 9
1
10
Sample Output 2:
13
10
Explanation Of Sample Input 2:
For the first test case:
The sub-array [9, 3, 1]  in the given ‘ARR’ has the maximum sum which is 13. Since ‘ARR’ is a circular array/list,  9 is connected to 3.

For the second test case:
The sub-array [10] in the given  ‘ARR’ has the maximum sum which is 10.
Hint

Try to use brute force approach in this problem

Approaches (2)
Brute Force

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’.
Time Complexity

O(N), where ‘N’ is the number of elements in the array/list ‘ARR’.

 

Because we are doing ‘N’ iterations 3 times so the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of elements in the array/list ‘ARR’.

 

Because we are using 3 extra arrays/lists each of size ‘N’ so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum Sum Circular Subarray
Full screen
Console