本文共 639 字，大约阅读时间需要 2 分钟。

1. 问题描述

最大连续子序列和问题，即是求给定序列中连续元素之和的最大值，例如给定序列a为：

{ -1, 2, 3, 7, -5, 4 }

那么最大子序列之和为12，子序列为 { 2, 3, 7 }.

2. 问题分析

我们使用动态规划来解决这道题，使用动态规划的思想就是要得到该问题的状态定义和状态转移方程，状态定义可以轻松得出：

• sum[ i ]：以第i个元素结尾的子序列之和

• sum[ i ] = max{ a[ i ], sum[ i - 1 ] + a[ i ] }

根据状态转移方程，就可以容易地得到以下代码：

int max_sub(int a[], int size) {  	int i;	int max = 0,sum = 0;	for(i = 0;i < size;i++)	{  		if(sum + a[i] < a[i])			sum = a[i];		else			sum += a[i];		if(max < sum)			max = sum;	}  	return max;}

转载地址：https://blog.csdn.net/huzhiyuan0000000/article/details/74937537 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！