这是前几天笔试时,考场上想出来的算法,但是算了两次都不一样,最后只好蒙了一个选项,悲催!
问题如下:
给定一个整数序列,例如 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数组里所有元素之和。