最大连续子序列和问题

本文记录最大连续子序列和问题的两种解法：前缀和方法和动态规划方法。

问题 ¶

从一个可能包含负数的整数数组中，找出其连续子数组的和的最大值。

例如，对于 [-2,1,-3,4,-1,2,1,-5,4] 来说，连续子数组 [4,-1,2,1] 的和最大，为 6 。

leetcode 题目 - 最大子序和

前缀和方法 ¶

前缀和 sum(i) 是指以位置 i 结尾的前缀子数组的求和结果：

如此，任意一个连续数组 [i..j] 之和可以表达为 sum(j) - sum(i-1) ：

对于一个确定的 j ，假设前缀和 sum(j) 已知。

要使右侧区间内数字之和最大，势必要求左侧前缀和 sum(i-1) 最小。

也就是，要找出 j 左边的前缀和的最小值，它可以在计算前缀和的过程中记录下来。

最后，对所有 j 找出其右侧区间的最大和，记录其中最大的即结果。

最大子序列和问题 - 前缀和方法 - C 语言实现

// 返回给定整数数组的最大连续子序列的和。
int LargestSumContiguousSubarray(int nums[], int length) {
    // Sum of 1..j
    int sum = 0;
    // Min value of sum(i), where i < j.
    int min = 0;
    // Max value of delta, where delta = sum(j) - min.
    int max = nums[0];

    for (int j = 0; j < length; j++) {
        sum += nums[j];
        int delta = sum - min;
        if (delta > max) max = delta;
        if (sum < min) min = sum;
    }
    return max;
}

时间复杂度是 O(n) ，空间复杂度是 O(1) 。

动态规划方法 ¶

任何连续数组，都可以表达为：以位置 i 结尾的连续数组。

假设函数 dp(i) 是所有以位置 i 结尾的连续数组的和的最大值。

由定义可知, nums[i] 是所考虑的连续数组的结尾元素，因此 dp(i) 必然包含 nums[i] 作为成分。

假设已知 dp(i-1)，考虑其递推到 dp(i)：

如果 dp(i-1) 是正数，考虑到要求最大和，因此将它吸收，即 dp(i) = dp(i-1) + nums[i]
否则，不吸收 dp(i-1) ，即 dp(i) = nums[i]

对所有 0..n-1 的 i 求解其 dp(i) ，找出其中最大值即结果。

最大子序列和问题 - 动态规划方法 - C 语言实现

// 返回给定整数数组的最大连续子序列的和。
int LargestSumContiguousSubarray(int nums[], int length) {
    if (length <= 0) return 0;

    int max = 0;
    int dp[length];
    dp[0] = nums[0];

    for (int i = 1; i < length; i++) {
        if (dp[i - 1] > 0)
            dp[i] = dp[i - 1] + nums[i];
        else
            dp[i] = nums[i];

        if (max < dp[i]) max = dp[i];
    }
    return max;
}

最大子序列和问题 - 动态规划方法 - C 语言实现 - 空间 O(1)

// 返回给定整数数组的最大连续子序列的和。
int LargestSumContiguousSubarraySpaceO1(int nums[], int length) {
    if (length <= 0) return 0;

    int dp = nums[0];
    int max = dp;

    for (int i = 1; i < length; i++) {
        if (dp > 0)
            dp += nums[i];
        else
            dp = nums[i];

        if (max < dp) max = dp;
    }
    return max;
}

时间复杂度是 O(n) ，空间复杂度是 O(n) 或 O(1)。

（完）

本文原始链接地址： https://writings.sh/post/algorithm-largest-sum-contiguous-subarray