Short linear time 12ms C++ solution with explanation


  • 3
    D

    The idea is to update two values as we scan through the array:

    The first value curr_mx is the maximum subarray sum ending at the current element. This is "reset" to simply be the current element if the maximum subarray sum ending at the current element ever becomes less than the current element (and hence doesn't produce a better sum than just using the current element).

    The second value mx is simply the running max of those maximum subarray sums across all elements.

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int curr_mx = 0, mx = std::numeric_limits<int>::min();
            for (int n : nums) {
                curr_mx = max(curr_mx + n, n);
                mx = max(mx, curr_mx);
            }
            return mx;
       } 
    };

Log in to reply
 

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