最大子段和 题解

思路

方法 1

考虑 dp。

分两种情况：

1. 这个数够大，自己成为一个子段。

2. 这个数和其他数进行组合。

显然两种情况取最大值。

没啥好说的，就是最小值设置成 0，因为可以啥也不选。

时间复杂度 $O(n)$。

方法 2

此题数据非常小，暴力能过。

枚举左端点和右端点，前缀和优化或者直接暴力加求区间和。

最后在所有区间和中取最大值。

时间复杂度 $O(n^2)$。

代码

别抄。

方法 1

#include <iostream>
#include <vector>
using namespace std;
int main(){
    long long ans=0;//这里很关键
    int n;
    cin >> n;
    vector<long long> a(n+1),s(n+1,0);
    for (int i=1;i<=n;++i){
        cin >> a[i];
        s[i]=max(a[i]/*自己够大*/,s[i-1]+a[i]/*和别人组合*/);
        ans=max(ans,s[i]);//边dp边比较
    }
    cout<<ans<<endl;
    return 0;
}

方法 2

这里我直接用的是暴力求区间和，可以用前缀和求区间和。

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i=0;i<n;++i){
		cin >> a[i];
	}
	int ans=0;
	for (int i=0;i<n;++i){
		for (int j=i;j<n;++j){
			int sm=0;
			for (int k=i;k<=j;++k){//这里我用的是[]区间 
				sm+=a[k];
			}
			ans=max(ans,sm);
		}
	}
	cout<<ans<<endl;
	return 0;
}