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:
Let's say the intervals are [0, ‘i’], [‘j’, ‘N’ - 1]. Let's try to compute both intervals:
We can optimize the previous approach because in this problem ‘ARR’ is a circular array. So there are the following two cases:
Here is the complete Algorithm:
Longest Subarray With Zero Sum
Merge Two Sorted Arrays Without Extra Space
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Negative To The End
Find Duplicate in Array