-
Notifications
You must be signed in to change notification settings - Fork 0
/
bestIndexSubSum.cpp
64 lines (47 loc) · 2.01 KB
/
bestIndexSubSum.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.
Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).
Example:
A : [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]
NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length
NOTE 2: If there is still a tie, then return the segment with minimum starting index
*/
vector<int> maxset(vector<int> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int startIndex = 0;
int endIndex = 0;
int bestStartIndex = 0;
int bestEndIndex = 0;
long long bestSum = INT_MIN;
long long sum = 0;
for (int i = 0; i < A.size(); ++i) {
if (A[i] < 0) {
startIndex = i + 1;
endIndex = startIndex;
sum = 0;
} else {
sum += A[i];
++endIndex;
if (sum > bestSum) {
bestStartIndex = startIndex;
bestEndIndex = endIndex;
bestSum = sum;
} else if (sum == bestSum && endIndex - startIndex > bestEndIndex - bestStartIndex) {
bestStartIndex = startIndex;
bestEndIndex = endIndex;
sum = 0;
}
}
}
vector<int> output;
for (int i = bestStartIndex; i < bestEndIndex; ++i){
output.push_back(A[i]);
}
return output;
}