文章目录

1. 1. 最长子序列和

最长子序列和

---

给定一组正数，需要求出这组数字中子序列之和最大值，当然这个子序列得是连续的，不然只需要把所有正数找出来求和即可。

比如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20；

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16；

序列：5 -3 4 2，则最大子序列和为8；

序列：5 -6 4 2，则最大子序列和为6。

这个问题的思路比较简单，从头开始加起，如果加上第i项后的和比前i-1项和要大，那么更新最大值并且继续往后加；如果加上第i项后的和小于0，那么当前最大值为0（需要保留之前求出的最大值），重新往后加，并和刚刚保留的最大值进行比较。

void longestSubsequenceSum(sequence[],length)
	int subSum=0; //当前子序列和
	int maxSum=0; //历史子序列的最大和
	for (int i = 0; i < length; i++)
	{
		subSum += sequence[i];
		if (subSum >= maxSum)
			maxSum = subSum;
		else if (subSum < 0)
			subSum = 0;
	}

很显然，这个算法的复杂度是线性的。