O(n) c++ solution


  • 1
    V

    class Solution {

    public:

    int maxSubArray(vector<int>& nums) 
    {
    
       int max = INT_MIN;
       //vector<int> results(nums.size(),0);
       int index =0;
       int prev_max = 0;
    
       for(vector<int>::iterator iter=nums.begin(); iter!=nums.end();iter++)
       {
    
           int value = *iter;
           if(index == 0)
           {
               if(value<0)
                  prev_max = 0; 
               else
                  prev_max = value;
               max = value;
           }
           else
    
           {
               int cur_max_sum = prev_max +value;
               if(cur_max_sum>max)
                   max = cur_max_sum;
               if(cur_max_sum>0)
                   prev_max = cur_max_sum;
               else
                   prev_max = 0;
           }
           
        index++;   
       }
       return max;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.