不重复子序列的个数

package org.sunny.dynamicProgram;

import java.util.Arrays;
import java.util.Scanner;

public class SubNumbers {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] iniarray = new int[num+1];
        int[] result = new int[num+1];

        //读入元素
        for (int i=1;i<=num;i++){
            iniarray[i] = scanner.nextInt();
        }
        System.out.println("elements---"+ Arrays.toString(iniarray));

        //标记最近一次元素出现的下标
        int[] flags = new int[Arrays.stream(iniarray).max().getAsInt()+1];


        /*我们知道如果不存在重复的数，那么dp[i]=dp[i-1]*2（含空集的情况）。
          现在考虑出现了重复的数。比如当前要取的数为a[i]，且a[i]最近一次在之前的j位置出现过了。
          那么有dp[i]=dp[i-1]*2-dp[j-1]。所以我们利用一个数组mark记录下
          a[i]出现的位置就好了，没有出现过为0。
         */
        for (int k=1;k<=num;k++){
            if (flags[iniarray[k]]==0){
                result[k] = result[k-1]*2+1;
            }
            else {

                result[k] = result[k-1]*2-result[flags[iniarray[k]]-1];
            }
            flags[iniarray[k]]=k;
        }

        System.out.println(result[num]);
    }
}