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

方法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;
}