一、问题描述

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

输入格式:

输入有两行：

第一行是n值（1<=n<=10000)；

第二行是n个整数。

输出格式:

输出最大子段和。

二、算法描述

该问题求解一个数组中的最大子段和，可以设一个数组dp[ ]通过填表的方式记录每一个子段的最大和，算法实现如下：

#include <iostream>

using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int dp[1000000];//定义dp[i]为从1加到i的最大子段和

int Sum(int a[], int n)

{

int record = 0;

for(int i = 1; i <= n; i++ )

{

if(record > 0)

    record += a[i];

else

    record = a[i];

dp[i] = max(dp[i - 1], record);

  

}

return dp[n];

}

int main(int argc, char** argv) {

int n;

cin >> n;

int a[n];

    bool flag = 0;

for(int i = 1; i <= n; i++)

    {

        cin >> a[i];

        if(a[i] > 0)//当输入的数组中有大于1的就将flag设为1

            flag = 1;

    }

    int result = Sum(a, n);

    if(flag == 0)

        cout << 0;//如果全都是负数就输出0

    cout << result;

return 0;

}

三、问题求解

1、根据最优子结构性质，列出递归方程式如下：

dp[i] = max(dp[i - 1], record)

其中，record表示从第一个非零整数加到第i个整数的和，如果已经小于零，则从新算

2、维度：求解的问题是一个以为数组，设置填表数组时也只需要一个一维数组即可；填表范围：为了防止段错误，设置长度时要尽可能大，但是也要避免溢出，而填表范围只需填到问题规模n即可；填表顺序：从1填到n

3、该算法的时间复杂度和空间复杂度

时间复杂度：求解这个问题主要是用到了一个for循环，所以该问题的时间复杂度为O(n)

空间复杂度：为了得到最优解，这个算法用了填表的方法，也就是借助了额外的空间，其空间复杂度为dp数组的大小

四、心得体会

这个问题并不算很难，主要还是找到递归方程式，对于所有都是负数的数组，可以利用一个布尔型变量去记录并且返回题目要求的0。但是在做这个题目的时候很久都没有写出正确的方程，导致一直出错。所以写代码之前还是要有个清晰的思路比较好

五、对动态规划算法的理解和体会

动态规划算法可以用来解决可以划分为更小的子问题的问题，主要是为了解决问题的复杂度和冗余度，通过求解子问题从而得到最优解。其中利用动态规划算法的核心还是根据最优子结构性质列出递归方程。