最大连续子序列和问题

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

问题

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

例如,对于 [-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-1i 求解其 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)

(完)

* * *
评论 首页 打印 ↑顶部