Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 19 Mar, 2021

Moderate

```
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.
```

```
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’.
```

```
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.
```

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

```
1 <= T <= 100
1 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5
Time Limit: 1 sec
```

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]*’.

- ‘

- Make an array/list ‘
- 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]*’.

- ‘

- Make an array/list ‘
- 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*’.

- Run a for loop from ‘

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*’.

Similar problems