Clean C++ Solution using Kadane's algorithm

programming
amazon
interview-questions
Tags: #<Tag:0x00007f181d7dcb98> #<Tag:0x00007f181d7dca58> #<Tag:0x00007f181d7dc8f0>

#1
int Solution::maxSubArray(const vector<int> &A) {
// To apply kadane's algorithm we need to have atleast one positive value.
// Case 1: If all values are negative, then we will return maximum of array.
// Case 2: There exists at least one positivem, then we will return maximum sum.
bool is_positive = false; // to check whether there exists atleast one positive value.
int sum = 0, max_sum = 0, neg_max = INT_MIN; //  sum-> current sum, max_sum -> max_sum till now
                                             // using kadane's algorithm and 
                                             // neg_max -> maximum of array if all elements are negative.
for(const int x:A){
    if(x>=0) is_positive = true; // positive element found
    sum = std::max(sum+x,0); // whether to add current element or return sum as 0 if sum becomes negative by adding current element.
    max_sum = std::max(sum,max_sum); // max_sum of array
    neg_max = std::max(neg_max,x); // maximum of array containing all negatives.
}
return is_positive?max_sum:neg_max;  // what to based on is_positive flag.

}