问题描述
给定n个整数组成的序列,求该序列所有子序列中和最大的一个。例如序列为 0,-1,-2,3,2 时,最大子序列为 3,2,最大值为5。
问题分析
我们先进行穷举,计算所有子序列,然后找出最大值。
我们用s(i,j)来表示起点为i,终点为j的子序列,遍历所有子序列时,先遍历起点i,时间复杂度O(n),再遍历终点j,复杂度也为O(n),对于每个子序列,i和j确定后,计算该序列的和也为O(n),故该方法的总时间复杂度为O(n^3)。
我们用一个矩阵来表示所有的子序列,如下所示:
0 | 1 | 2 | … | n-1 |
---|---|---|---|---|
s(0,0) | s(0,1) | s(0,2) | … | s(0,n-1) |
0 | s(1,1) | s(1,2) | … | s(1,n-1) |
0 | 0 | s(2,2) | … | s(2,n-1) |
… | … | .. | … | … |
0 | 0 | 0 | … | s(n-1,n-1) |
我们的目标就是计算出这个矩阵,然后找出最大值,穷举法的计算过程是从左向右,从上到下。观察到,每个子序列都可以由之前已经计算出的序列得到。例如 s(0,1)=s(0,0) + nums[1],我们可以得到下面这个公式:
穷举时,我们每一项都要重新计算,现在我们每一项只需要常数时间就可以计算出,此时时间复杂度为O(n^2)。
我们可以比较一下两个算法的时间:
|
|
可以看到当序列长度为1000时,相差已经很大了。