4
递增子序列数目计算的算法
source link: https://byronhe.com/post/2011/10/17/inc-sub-seq-count-algo/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
递增子序列数目计算的算法
2011-10-17
这是前几天笔试时，考场上想出来的算法，但是算了两次都不一样，最后只好蒙了一个选项，悲催！
问题如下：
给定一个整数序列，例如 4,2,6,3,7,1 ，该序列有多少个递增子序列？
我的算法如下：
记第i个元素为arr[i] ，记以第i个元素结尾的递增子序列有N[i]个，
则，考虑以第i+1个元素结尾的所有递增子序列，
首先置N[i+1]=1;//表示只有第i+1个元素一个元素的子序列。
对j=1...i
如果arr[j]<arr[i+1]
N[i+1]+=N[j]
最后结果等于N数组里所有元素之和。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK