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