1007 maximum subsequence sum

最大子序列和问题是指在一个序列中，找到一个连续的子序列，使得该子序列的和最大。这个问题可以用动态规划或分治法来解决。动态规划的思路是，从前往后遍历序列，对于每个位置，计算以该位置为结尾的最大子序列和，然后取所有位置的最大子序列和的最大值即可。分治法的思路是，将序列分成左右两部分，分别求出左半部分的最大子序列和、右半部分的最大子序列和和跨越中点的最大子序列和，然后取三者的最大值即可。

相关问题

1007 maximum subsequence sum (25 分)

题目描述

给定K个整数组成的序列{ N1, N2, ..., NK}，“连续子列”被定义为{ Ni, Ni+1, ..., Nj}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{-2, 11, -4, 13, -5, -2}，其连续子列{ 11, -4, 13}有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

输入格式

输入第1行给出正整数K（≤100000）。第2行给出K个整数，其间以空格分隔。

输出格式

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例

6
-2 11 -4 13 -5 -2

输出样例

20

思路分析

本题是最大子序列和问题，可以使用动态规划来解决。设dp[i]表示以第i个数结尾的最大子序列和，则有状态转移方程：dp[i] = max(dp[i-1]+a[i], a[i])，其中a[i]表示第i个数。

时间复杂度：O(n)

空间复杂度：O(n)

代码实现

完成 Maximum Subsequence Sum 的c语言代码

下面是一个使用动态规划解决 Maximum Subsequence Sum 问题的 C 语言代码：

#include <stdio.h>

int maxSubseqSum(int a[], int n)
{
    int maxSum = 0, thisSum = 0;
    for (int i = 0; i < n; i++) {
        thisSum += a[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) {
            thisSum = 0;
        }
    }
    return maxSum;
}

int main()
{
    int a[] = { -2, 11, -4, 13, -5, -2 };
    int n = sizeof(a) / sizeof(a[0]);
    int maxSum = maxSubseqSum(a, n);
    printf("Max subsequence sum: %d\n", maxSum);
    return 0;
}

这个代码中，maxSubseqSum 函数接受一个整数数组和数组长度作为参数，返回最大子序列和。函数中使用两个变量 maxSum 和 thisSum 分别记录全局最大子序列和和当前连续子序列的和。遍历数组中的每个元素，更新 thisSum 的值，如果 thisSum 大于 maxSum，则更新 maxSum 的值。如果 thisSum 小于 0，则将其重置为 0，从下一个元素重新开始计算。最终返回 maxSum 的值。

在 main 函数中，我们定义了一个整数数组 a，调用 maxSubseqSum 函数计算最大子序列和，并输出结果。