leetcode.53最大子序和

1、问题描述

1、动态规划

int max(int a, int b){
    return a>b?a:b;
}
int maxSubArray(int* nums, int numsSize){
    int dp[numsSize];
    int res = nums[0];
    dp[0] = nums[0];
    for(int i=1; i<numsSize; i++){
        dp[i] = max(dp[i-1]+nums[i],nums[i]);
        res = max(res,dp[i]);
    }
    return res;
}

2、贪心算法

int max(int a, int b){
    return a>b?a:b;
}
int maxSubArray(int* nums, int numsSize){
    int sum;
    int res=nums[0];
    for(int i=0; i<numsSize; i++){
        sum = max(sum+nums[i],nums[i]);
        res = max(res,sum);
    }
    return res;
}

3、运行用时4ms范例

它这里的思想也是用到贪心算法。只要tmp为负数， 那在进行下一次循环前tmp都初始化为0.因为tmp为负数时，加任何数都是会变小的。因此我们不必保存负数。