PAT甲级 1007 Maximum Subsequence Sum 25 分

• 题目
• 思考
• 代码

题目

原题描述

即：找到一个字符串的和最大的连续子序列，输出：和，子序列开始元素，子序列结束元素

若子序列全为负数，则输出：0，数组开头元素，数组结束元素

思考

动态规划

sum[i]表示的是以a[i]元素结尾的连续子序列的最大和

状态转移方程： sum[i] = max (sum[i-1]+a[i], a[i])

代码

#include<stdio.h>
#include <algorithm>
#include<string.h>
using namespace std;

int K[10001];
int a[10001];

int main(){
	int n,max;
	int first,last ,i,maxA,z sumA;
	int maxFirst, maxLast;
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%d",&K[i]);
			a[i] = K[i];
		}
		sort(a,a+n);
		max = a[n-1];
		if(max < 0){
			printf("0 %d %d",K[0],K[n-1]);
			return 0;
		}
		maxA = K[0]; sumA = K[0]; 
		first = last = 0;
		maxFirst = maxLast = 0;
		for(i = 1; i< n; i++){
			if(sumA + K[i]> K[i]){
				sumA = sumA + K[i];
				last ++;
			}else{
				first = last = i;
				sumA = K[i];
			}
			if(sumA > maxA){
				maxA = sumA;
				maxFirst = first;
				maxLast = last;
			}
		}
		printf("%d %d %d", maxA, K[maxFirst], K[maxLast]) ;
		return 0;
	}
	return 0;
}