动态规划 专题

PAT A1007 Maximum Subsequence Sum (25’)

题目

思路

三种情况

  • 最大连续子序列和唯一：输出最大值，以及首尾两个元素
  • 最大连续子序列和不唯一：输出最大值，以及最小的首尾两个元素
  • 最大连续子序列每个元素都是负数：输出 0，以及首尾两个元素

递推关系

  • dp[i-1] > 0: dp[i] = dp[i-1]+num[i];
  • else: dp[i] = num[i];

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int num[10100],dp[10100];
bool flag = false;

int main(){
	int k;
	scanf("%d", &k);
	int left[10100],right;  //首尾下标 
	for(int i = 1; i <= k; ++i){
		scanf("%d", &num[i]);
		if(num[i] >= 0){
			flag = true;  //存在非负数，就置为 true 
		}
	}
	if(flag == false){  //全为负数 
		printf("0 %d %d\n",num[1],num[k]);
		return 0;
	}
	memset(dp,0,sizeof(dp)); 
	dp[0] = num[0];  //边界 
	for(int i = 2; i <= k; ++i){
		if(dp[i-1] > 0){  //如果前一个子序列和为正数，则加入其中 
			dp[i] = dp[i-1]+num[i];
			left[i] = left[i-1];  //当前子序列的首部元素下标继承了前一个子序列的首部元素下标 
		}
		else{
			dp[i] = num[i];  //子序列就是它本身 
			left[i] = i;
		}	
	}
	int sum = -1;
	for(int i = 2; i <= k; ++i){  //从第二个开始 
		if(sum < dp[i]){
			sum = dp[i];
			right = i; 
		}
	}
	printf("%d %d %d\n",sum,num[left[right]],num[right]);
	return 0;
}

注：有一个测试点过不了。