如果求最大非连续子序列？？

Question

假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S

Answer 1

public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
    // Write your solution here
    if (sequence.isEmpty()) return new ArrayList<Integer>();
    int max_size[] = new int[sequence.size()];
    int prev_index[] = new int[sequence.size()];
    max_size[0] = 1;
    prev_index[0] = -1;
    for (int i = 1; i < sequence.size(); i++) {
        int cur_max = 1;
        int cur_prev = -1;
        int iVal = sequence.get(i);
        for (int j = i - 1; j >= 0; j--) {
            if (cur_max < max_size[j] + 1 && sequence.get(j) < iVal) {
                cur_max = max_size[j] + 1;
                cur_prev = j;
            }
        }
        prev_index[i] = cur_prev;
        max_size[i] = cur_max;
    }
    int max_idx = sequence.size() - 1;
    int max_val = max_size[max_idx];
    for (int i = max_idx - 1; i >= 0; i--) {
        if (max_val < max_size[i]) {
            max_idx = i;
            max_val = max_size[i];
        }
    }
    List<Integer> aList = new ArrayList<Integer>();
    int idx = max_idx;
    aList.add(sequence.get(idx));
    while (prev_index[idx] >= 0) {
        idx = prev_index[idx];
        aList.add(sequence.get(idx));
    }
    List<Integer> retList = new ArrayList<Integer>(aList.size());
    for (int i = aList.size() - 1; i >= 0; i--) {
        retList.add(aList.get(i));
    }
    return retList;
}