最长字段和问题

p1115
这次我初次接触dp时做的一道题，这么久以来又刷到了这道经典的dp问题，但是现在在重新审视这道题发现，这道题的做题思路居然不是dp方程动态规划来求解，更像是贪心，用一种局部最优来达到整体最优的一种方式。
弱鸡代码
第一种方法，利用dp方程的方式，显然二维的空间过大，不符题意，只能降为一维求解，弱鸡的我不会。
dp方程dp[i][j]=dp[i-1][j-1]+a[j];
利用便利所有情况的dp方程虽然感觉很暴力，其实粗略计算一下时间复杂度其实不高，勉强能够通过，无奈空间复杂度不满足。。

#include//最大字段和，dp方程
using namespace std;
int dp[2001][2001];//为什么放在main函数里会运行出错
int main()
{
int n,i,j;
int a[2002];

cin>>n;
long int max=0;
for(i=0;i<n;i++){
cin>>a[i];
dp[0][i]=a[i];
if(a[i]>max)
{
max=a[i];
}
}
for(i=1;i<n;i++){
for(j=i;j<n;j++){
dp[i][j]=dp[i-1][j-1]+a[j];
//cout<<"i:"<
if(dp[i][j]>max)
{
max=dp[i][j];
//cout<
}
}}
cout<<max<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

ac代码
贪心的思路
实际就是判断，和当前数相加是否大于0，若大于0则表示，前面的数加现在的数在和接下来的数相加仍然可能获得较大的一个数，再判断当前数是否大于目前的最大的数之和即可（贪心的思路还是比较简单的，有一个坑就是，有可能刚好所有数之和都小于0的情况）。

#include//最大字段和，dp方程，经过思考发现用贪心思想即可，
//#include 
using namespace std;
int main()
{
//ifstream cin;
//cin.open("c:\\test.txt", ios::in);
int n,i,j;
int a[200005];
cin>>n;
int max=-10000001;
for(i=0;i<n;i++){
cin>>a[i];
}
//cout<
int sum=0;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
sum=a[j]+sum;
if(sum>=0||sum>max)
{
if(sum>max)
{
max=sum;
}
}else
{
break;
}
}
sum=0;
}
cout<<max<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35