3-4 lines Ruby and C++

  • 0

    Walk straight over the input array. Let best hold the best sum found overall and curr hold the best sum ending with the current element. For the latter, we can either use the current element alone (that's n) or also use the best sum ending with the previous element (that's curr+n, with the previous value of curr).


    def max_sub_array(nums)
        best, curr = nums[0], 0
        nums.each { |n| best = [best, curr = [n, curr+n].max].max }


    int maxSubArray(vector<int>& nums) {
        int best = nums[0], curr = 0;
        for (int n : nums)
            best = max(best, curr = max(n, curr+n));
        return best;

Log in to reply

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