A simple O(n) time and O(1) space algorithm


  • 0
    M

    I saw many people talked about DP or greedy, I think those methods are great but just make the simple problem complex, my idea is that:
    keep calculating the sum from 0 to i, and use 'min' to keep track of the minimum sum so far, and find the maximum of each current sum minus 'min', that will be our answer, code blow:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int size=nums.size();
            if(size<1)
            return 0;
            int sum=0,min=0,max=INT_MIN,n=-1;
            for(int i=0;i<size;i++){
                sum+=nums[i];
                if(i>n){
                    if(sum-min>max)
                    max=sum-min;
                }
                if(sum<min){
                    min=sum;
                    n=i;
                }
            }
            return max;
        }
    };
    

Log in to reply
 

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