连续子数组的最大和

题目链接: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

image.png

题目解析

动态规划解析
动态规划

public int maxSubArray(int[] nums) {
    // f(n) = f(n-1) + n

    // 如果f(n-1)<0就是负贡献，赋值f(n) = n
    // 如果f(n-1)>=0 正贡献, 赋值 f(n) = f(n-1) + n

    //fn1表示f(n-1)
    int fn = nums[0], fn1 = 0;

    int max = fn;
    for (int i = 1; i < nums.length; i++) {
        fn1 = fn;
        int n = nums[i];
        if (fn1 < 0 ){
            fn = n;
        }else {
            fn = fn1 + n;
        }
        max = Math.max(max,fn);
    }
    return max;

}

复杂度分析
空间复杂度: O(1)。
时间复杂度: O(n)。