Given an circular integer array (the next element of the last element is the first element), find a continuous subarray in it, where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number.
If duplicate answers exist, return any of them.
Have you met this question in a real interview?
Yes
Example
Give[3, 1, -100, -3, 4], return[4,1].
line 29 , line 50 parameter start and end should be int reference , forget it
line 24 range is not minStart, minEnd
line 21should use
>
=
and should exclude special case whole arrays are negative values case
class Solution {
public:
\*\*
* @param A an integer array
* @return A list of integers includes the index of
* the first number and the index of the last number
*/
vector<int> continuousSubarraySumII(vector<int>& A) {
// Write your code here
if (A.empty()) {
return vector<int>({-1, -1});
}
int maxStart = -1, maxEnd = -1;
int maxVal = findMaxSubarraySum(A, maxStart, maxEnd);
int minStart = -1, minEnd = -1;
int minVal = findMinSubarraySum(A, minStart, minEnd);
int allsum = 0;
for (auto& val : A) {
allsum += val;
}
if (maxVal >= allsum - minVal || (minStart == 0 && minEnd == A.size() - 1)) {
return vector<int>({maxStart, maxEnd});
} else {
return vector<int>({minEnd + 1, minStart - 1});
}
}
private:
int findMaxSubarraySum(const vector<int>& A, int& start, int& end) {
int left = 0, right = 0;
start = 0, end = 0;
int maxSum = A[0], sumSofar = A[0];
for (int i = 1; i < A.size(); ++i) {
if (sumSofar >= 0) {
sumSofar += A[i];
} else {
sumSofar = A[i];
left = i;
}
right = i;
if (sumSofar > maxSum) {
maxSum = sumSofar;
start = left;
end = right;
}
}
return maxSum;
}
int findMinSubarraySum(const vector<int>& A, int& start, int& end) {
int left = 0, right = 0;
start = 0, end = 0;
int minSum = A[0], sumSofar = A[0];
for (int i = 1; i < A.size(); ++i) {
if (sumSofar <= 0) {
sumSofar += A[i];
} else {
sumSofar = A[i];
left = i;
}
right = i;
if (sumSofar < minSum) {
minSum = sumSofar;
start = left;
end = right;
}
}
return minSum;
}
};