Share my 8ms c++ o(n) solution


  • 1
    W
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int res=nums[0], rightMost=nums[0];
            for(int i=1;i<nums.size();i++){
                if(rightMost<0)
                    rightMost=nums[i];
                else
                    rightMost+=nums[i];
                if(rightMost>res)
                    res=rightMost;
            }
            return res;
        }
    };

  • 0
    Z

    Could you plz explain your code?


  • 0
    W

    Sure. Firstly, the key thing of this problem is obviously how to update the largest sum. In my solution, I have two main variables, res and rightMost. For each i in my loop, I will compare the largest contiguous subarray sum, which is current value of "res", and the largest contiguous subarray sum ended at index of i, i.e. the subarray {nums[k],nums[k+1],...,nums[i]} where k belong to [0,i] and make the sum of this subarray largest. This sum will be stored in the variable "rightMost". It is very straightforward that for each i, if res is smaller than rightMost+nums[i], then res is updated to rightMost+nums[i]. Otherwise, the res won't change but we still need update the value of rightMost. But the previous value of rightMost is possible to be negative so that rightMost+nums[i]<nums[i], then the updated rightMost should be nums[i] rather than rightMost+nums[i]. So after finishing this loop from 1 to nums.size(), we can get the final res. Hope my explaination is clear.


Log in to reply
 

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