贪心算法：最大子序和

/*
给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
*/
int maxSubArray(int* nums, int numsSize){
    int temp = 0, ret = nums[0];
    for(int i = 0; i < numsSize; i++){
        temp = fmax(temp + nums[i], nums[i]);
        ret = fmax(temp, ret);
    }
    return ret;  
}

动态规划：最大子序和

/* 解法1： */
int maxSubArray(int* nums, int numsSize){
    /* 1、若数组为空，返回0 */
    if (numsSize == 0) {
        return 0;
    }
    /* 2、确定base case */
    int *dp = (int*)malloc(sizeof(int) * numsSize);
    dp[0] = nums[0];
    /* 3、确定状态转移方程
     * 状态：以当前节点结束的最大子序列和
     * 选择：每个节点
     * 状态转移方程：dp[i] = dp[i] > dp[i - 1] + nums[i] ? dp[i] : dp[i - 1] + nums[i]
     */
    for (int i = 1; i < numsSize; i++) {
        dp[i] = nums[i] > (dp[i - 1] + nums[i]) ? nums[i] : (dp[i - 1] + nums[i]);
    }
    /* 4、找出最大的子序列和 */
    int res = -INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        res = res > dp[i] ? res : dp[i];
    }
    /* 5、返回最大子序列的和 */
    return res;
}





图片会有广告。。。