14-line 4 ms C solution, easy understand


  • 1

    Initialize 't' =0, 'max'=s[0];

    Only when t > 0, 't' is a valid number, let t plus s[i]. Else reset t = s[i].

    int maxSubArray(int* s, int ns)
    {
    	int t = 0;
    	int max = s[0];
    	for (int i = 0; i < ns; ++i)
    	{
    		if (t>0)
    			t += s[i];
    		else
    			t = s[i];
    		max = max > t ? max : t;
    	}
    	return max;
    }
    

    PS: May be the above solution is suitable for this problem (partly because this problem is not difficult), but it not a general DP solution. For example when come to #188 Best Time to Buy and Sell Stock IV. The followed DP solution is useful for this problem and #188

    int maxSubArray(vector<int>& a) 
    {
    	if (a.empty())
    		return 0;
    	int sz = a.size();
    	int local; //when a[i] has been used, in this situation, the max value
        int global; //final max value; global has a choice: whether add a[i] into calculation.
    	global = local = a[0]; 
    	int i;
    	for (i = 1; i < sz; ++i)
    	{
    		local = max(local + a[i], a[i]); //'a[i]' means abandon a[i-1], restart from a[i]; 'local + a[i]' means a[i-1] and a[i] all will be adopted.
    		global = max(global, local); //whether add a[i] into calculation.
    	}
    	return global;
    }

Log in to reply
 

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