-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMax Non Negative SubArray
More file actions
65 lines (56 loc) · 1.63 KB
/
Max Non Negative SubArray
File metadata and controls
65 lines (56 loc) · 1.63 KB
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
65
Max Non Negative SubArray
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> Solution::maxset(vector<int> &A)
{
int n = A.size();
int i=0,start=0,end=-1;
int count=0,maxm=0; // for counting the length of subarray
int fstart=-1,fend=-1;
long long int sum=0,maxsum=0;
vector<int> result;
while(i<n)
{
if(A[i] >= 0)
{
sum+=A[i];
count++;
end++;
}
if (sum > maxsum)
{
maxsum = sum;
fstart = start;
fend = end;
}
else if(sum==maxsum && count > maxm)
{
maxm = count;
fstart = start;
fend = end;
}
if(A[i] < 0)
{
count = 0;
start = i+1;
end = i;
sum =0;
}
i++;
}
if(fstart!=-1 && fend!=-1)
{
for(int i=fstart; i<=fend; i++)
{
result.push_back(A[i]);
}
}
return result;
}