PAT-A1007(C/C++代码解析)

1007 Maximum Subsequence Sum (25 分)

注：简单题

法一：双循环

#include  
const int maxn=888888;
int z[maxn];
int main ()
{
    int i,j,n,sum,lmax=-1,last,first,flag=0;
    scanf ("%d",&n);
    for (i=0;i=0)
    	flag=1;
	}
	if (flag==0)
	printf ("0 %d %d",z[0],z[n-1]);
	else
	{
		for (i=0;ilmax)
				{
					lmax=sum;
					first=z[i];
					last=z[j];
				}
			}
		}
		printf ("%d %d %d",lmax,first,last);
	}
    return 0;
}

法二：动态规划

#include 
#include 
using namespace std; 
const int maxn=888888;
int z[maxn],dp[maxn],f[maxn];
int ss(int i,int j)
{
	int k,sum=0;
	for (k=i;k<=j;k++)
	sum=sum+z[k];
	return sum;
}
int main ()
{
    int i,j,n,sum,lmax=-1,last,first,flag=0;
    scanf ("%d",&n);
    for (i=0;i=0)
    	flag=1;
	}
	i=0,j=0;
	if (flag==0)
	printf ("0 %d %d",z[0],z[n-1]);
	else
	{
		dp[0]=z[0];
		f[0]=0;
		for (i=1;i=z[i])
			{
				dp[i]=dp[i-1]+z[i];
				f[i]=f[i-1];
			}
			else
			{
				dp[i]=z[i];
				f[i]=i;
			}
		}
		int k=0;
		for (i=0;idp[k])
			k=i;
		}
		printf ("%d %d %d",dp[k],z[f[k]],z[k]);
	}
    return 0;
}