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

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

问题如下：

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