Context
Max Slice Problem
Given an array of integers, find a contiguous slice in the array that has max sum in O(N) worst case time complexity and O(1) worst case space complexity
Solution is already explained here but needs some tweaking
My Solution
#include
int solution(vector<int> &A) {
if(!A.empty()){
int maxsum=A[0], maxend=A[0];
for(int x=1; x < A.size(); x++){
if( A[x] < 0 && A[x] > maxend) \\ this is a negative number
maxend = A[x];
else \\ this is a positive number
maxend = std::max(A[x], maxend+A[x]);
maxsum = std::max(maxend, maxsum);
}
return maxsum;
}
else
return 0;
}
Learning