当前位置:   article > 正文

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

递增子序列的总个数

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

问题如下:

给定一个整数序列,例如 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数组里所有元素之和。

转载于:https://www.cnblogs.com/windydays/archive/2011/10/17/2298105.html

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/521430
推荐阅读
相关标签
  

闽ICP备14008679号