求连续子数组的最大和

http://www.nowcoder.com/questionTerminal/8705437354604a7cb9ba7bf959e42de6

题目难度：二星
考察点：字符串、动态规划

方法1：暴力

1.分析：

根据题意进行暴力计算，即枚举一个区间的起始位置i和结束位置j，然后计算区间[i,j]之间的和sum，一共是n*(n+1)/2个区间，在这么多区间的和选出一个最大值作为结果输出即可。但是这里有一个比较难的就是输入的是一个字符串，所以要将字符串转化为整数数组的形式，在前一个题解中已经介绍了stringstream的用法，在这里就还是用stringstream来处理，即首先ss>>x，读入一个整数x，往后的形式都是一个字符","加上一个整数，那么就可以写作while(ss>>ch>>x) a[n++] = x;此时数组a中就是我们要进行计算的数。

算法实现：
(1). 输入字符串s，定义stringstream对象ss(s);
(2). 得到需要计算结果的数组a;
(3). 枚举区间起始位置i和结束位置j，并计算区间[i,j]中的和，并比较大小，保留最大值。
(4). 输出最大值ans。

2.复杂度分析：

时间复杂度：O(n^3)
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
int a[MAXN];
int main() {
    string s; cin>>s;
    stringstream ss(s);
    int x, n = 0;
    char ch;
    ss >> x;
    a[n++] = x;
    while(ss>>ch>>x) a[n++] = x;
    int ans = 0;
    for(int i=0; i<n; i++) {
        for(int j=i; j<n; j++) {
            int sum = 0;
            for(int k=i; k<=j; k++) sum += a[k];
            ans = max(ans, sum);
        }
    }
    cout<<ans<<endl;
    return 0;
}

方法2:动态规划

1.分析：

虽然上述算法也能过这道题，但是算法的时间复杂度太高，接下来我们想办法进行优化这个问题，采用动态规划的思想，定义dp[i]表示以i结尾的连续子数组的最大值。那么就有如下动态转移方程成立:
dp[i] = max(a[i], dp[i-1]+a[i])，我们得到所有的dp[i]值之后，在这里面选出最大的值作为连续子数组的最大和结果输出。

算法实现：
(1). 输入字符串s，定义stringstream对象ss(s);
(2). 得到需要计算结果的数组a;
(3). 进行一次循环，然后根据状态转移方程计算dp[i]的值
(4). 比较所有的dp[i],输出最大值ans。

2.复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
int a[MAXN], dp[MAXN];
int main() {
    string s; cin>>s;
    stringstream ss(s);
    int x, n = 0;
    char ch;
    ss >> x;
    a[n++] = x;
    while(ss>>ch>>x) a[n++] = x;
    dp[0] = a[0];
    for(int i=1; i<n; i++) dp[i] = max(dp[i-1]+a[i], a[i]);
    int ans = 0;
    for(int i=0; i<n; i++) ans = max(ans, dp[i]);
    cout<<ans<<endl;
    return 0;
}