无序数组及其子序列的相关问题研究(2)

我们假设count(i)表示以nums[i]结尾的递增子序列个数. 则对于前置无序数组nums而言, 它的所有递增子序列的个数, 就是以nums[i]结尾的递增子序列的和, 表示为sum(count(i))(0 < i < n - 1).

理解了以上假设, 那么我们可以发现以下规律: 

count(0) = 1;

count(1) = 1; (nums[0] > nums[1])

count(2) = 1 + count(0) + count(1) (nums[0] < nums[2], nums[1] < nums[2])

= 1 + 1 + 1 = 3;

所以, nums的所有递增子序列个数就是count = count(0) + count(1) + count(2) = 1 + 1 + 3 = 5;

因而, 我的思路是: 建立一个数组counts = new int[nums.length + 1]用于保存以nums[i]结尾的递增子序列的个数, 即counts[i] = count(i). 而counts[nums.length]则用于累积counts[i], 表示整个序列的递增子序列的个数.

上述思路的Java实现如下: 

public int countIncreasingSubsequences(int[] nums){
    if (nums == null){
        return -1;
    }
    int[] counts = new int[nums.length + 1];
    for(int i = 0; i < nums.length; i++){
        counts[i] = 1;//单元素递增序列计数
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                counts[i] += counts[j];
            }
        }
        counts[nums.length] += counts[i];
    }
    return counts[nums.length];
}

问题4:

求它的所有递增子序列. 例如前置无序数组的所有递增子序列为[2], [1], [1, 3], [2, 3], [3].

分析:

需要利用动态规划思想来分析这道题目. 其实, 大体思路跟求它的所有子序列相同, 只不过是本问题要求子序列是递增的, 所以, 就利用递增来修改求所有子序列的逻辑.

因而, 对于元素nums[i], 我们将它的所有子序列表示为subs(i). 那么对于nums[i-1]和nums[i], 则存在这些一个关系:

subs(i) = [nums[i], (sub + nums[i])], 其中满足限制条件 sub in subs(i - 1) & sub.lastElement < nums[i]. 

上述表达式想要表达的意思是: subs(i)生成的所有递增子序列, 由nums[i]和subs(i - 1)生成的所有末尾元素小于nums[i]的递增子序列末尾加上nums[i]组成.

由此, 依据这种思路, 即利用动态规划思想生成所有递增子序列, 可以利用如下java代码实现:

public List<List<Integer>> allIncreasingSubsequences(int[] nums){
    if (nums == null){
        return null;
    }
    List<List<Integer>> result = new ArrayList<>();
    for(int num : nums){
        List<List<Integer>> tmp = new ArrayList<>();
        List<Integer> firstList = new ArrayList<>();
        firstList.add(num);
        tmp.add(firstList);
        for(List<Integer> list : result){
            if(list.get(list.size() - 1) < num){
                List<Integer> newList = new ArrayList<>(list);
                newList.add(num);
                tmp.add(newList);
            }
        }
    }
    return result;
}

最后, 关于递减子序列的问题, 原理跟递增子序列问题是一样的, 这里就不再赘述, 有兴趣的同学, 可以自己手动写一下.