Sunday 17 July 2016

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

 vector<int> Solution::maxset(vector<int> &A) {  
   int len = A.size();  
   long long maxSum = 0;  
   long long curSum = 0;  
   int startMax = -1;  
   int endMax = -1;  
   int start = 0;  
   int end = 0;  
   while(end < len) {  
    if(A[end] >= 0) {  
      curSum += (long long)A[end];  
      if(curSum > maxSum) {  
           maxSum = curSum;  
           startMax = start;  
           endMax = end + 1;  
      } else if(curSum == maxSum) {  
           if(end + 1 - start > endMax - startMax) {  
               startMax = start;  
              endMax = end + 1;  
           }  
      }  
    }else {  
      start = end + 1;  
      curSum = 0;  
    }  
    end++;  
   }  
   vector<int> ans;  
   ans.clear();  
   if(startMax == -1 || endMax == -1)  
     return ans;  
   for(int i = startMax; i < endMax; ++i)  
      ans.push_back(A[i]);  
   return ans;  
 }  
Share:

1 comment:

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive