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?
Anuttar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.