O(n), 70%, 8ms, short C++ code


  • 2

    The basic idea is that, check the sum in the loop, record and update the minimum sum. Each time we compare the difference of current sum and the minimum sum, the largest difference is obviously the result.

    class Solution {
        public:
            int maxSubArray(vector<int>& nums) {
                int SUM = nums[0], minSum = 0, value = nums[0];
                for( int i=1; i<nums.size(); i++ ) {
                    if( SUM < minSum )  minSum = SUM;
                    SUM += nums[i];
                    if( SUM - minSum > value ) value = SUM - minSum ;
                }
                return  value;
            }
    };

  • 0
    S
    This post is deleted!

Log in to reply
 

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