The problem is stated as following: Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) mod n] and the previous element of nums[i] is nums[(i - 1 + n) mod n]. A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 mod n == k2 mod n.
Now, I searched for the solution on the internet and found that the subarray (say A) formed by all the elements not belonging to the subarray (say B) with maximum possible sum forms the subarray with minimum possible sum. I am not able to grasp this logic. Can someone please explain how it works?
I tried to prove the statement by contradiction but cant draw any conclusion. Moreover, I cant understand why subarray A needs to be the minimum possible sum, why not something between minimum and maximum?
the subarray (say A) formed by all the elements not belonging to the subarray (say B) with maximum possible sum forms the subarray with minimum possible sum.
This is true. Let 𝑆 be the sum of all elements in the input array. And let 𝑀 be the maximum sum formed by subarray 𝐵, then surely the sum of the subarray 𝐴 is 𝑆−𝑀.
If 𝐴 would not represent a subarray with minimum sum, then there would be another subarray 𝐶 that had a lesser sum than 𝐴. But then the sum of the values not in 𝐶 would be greater than 𝑀, which is a contradiction, because we started out by the given fact that 𝐵 is the subarray with maximum sum.