C++ solution with dynamic programming equation in detail.


  • 0
    C

    in fact, i go to solve this problem with the below equation:
    dp[i]=max(dp[i-1]+value[i],value[i])
    dp[i] : means that the max sum beform i
    value[i]: means the value of i
    so this equation means:
    if the previous max sum plus value of i is much max than value of i, so i chose the former.
    because when we add value i ,the whole sum can be much max.
    but if not
    that means the previous sum has negative influence on the value , so i just chose value as the sum

    int maxSubArray(vector<int>& nums) {
    	int max = 0;
    	int temp;
    	int premax = nums[0];
    	int realmax = nums[0];
    	for (int i = 0; i < nums.size(); i++)
    	{
                   //means max(premax+nums[i],nums[i])
    		temp = (((premax)+nums[i])>nums[i] ? ((premax)+nums[i]) : nums[i]);
    		max = temp;
    		premax = max;
    		if (realmax < max)
    			realmax = max;
    	}
    	return realmax;
    }
    

Log in to reply
 

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