Easy and clean O(1) space and O(n) time C++ solution.


  • 0
    X

    Solution shown below is according to Book - Introduction to Algorithms, which originally uses divide and conquer to solve this problem and offers an idea towards linear time algorithm.

    int maxSubArray(vector<int>& nums) {
            int rst = INT_MIN;
            int preMax = INT_MIN;
            
            for (int i = 0; i < nums.size(); ++i) {
                int curMax = (preMax <= 0) ? nums[i] : nums[i]+preMax;
                rst = max(rst, curMax);
                preMax = curMax;
            }
            return rst;
        } 
    

Log in to reply
 

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