Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

递增子序列数目计算的算法

这是前几天笔试时,考场上想出来的算法,但是算了两次都不一样,最后只好蒙了一个选项,悲催!

问题如下:

给定一个整数序列,例如 4,2,6,3,7,1 ,该序列有多少个递增子序列?

我的算法如下:

记第i个元素为arr[i] ,记以第i个元素结尾的递增子序列有N[i]个,

则,考虑以第i+1个元素结尾的所有递增子序列,

1
2
3
4
5
6
7
8

首先置N[i+1]=1;//表示只有第i+1个元素一个元素的子序列。

对j=1...i

           如果arr[j]<arr[i+1]

                  N[i+1]+=N[j]

最后结果等于N数组里所有元素之和。