目录

最长上升子序列(LIS)

Longest Increasing Subsequence,LIS, 最长上升子序列

题目

给定n个数字的序列,如11,3,6,9,13,8,问最长的上升序列上升子序列是什么。 上升序列,分为严格单调递增序列和单调不减序列。前者需满足序列L中,i<j, L[i]<L[j],而后者可取等号。

解题思路

https://gitee.com/lienhui68/picStore/raw/master/null/20200702130938.png

递增的判断都是在原序列末尾元素基础上进行比较的,是动态规划典例。

  1. 状态设计

    f(x)表示以a[x]结尾的LIS长度,那么LIS=max{f(x)}

  2. 状态转移方程

    考虑比x小的每一个p,如果a[x]>a[p],那么f(x)=f(p)+1,所以f(x)=max{f(p)} + 1,其中p<x且a[p]<a[x]

    如果找不到比x小的p,那么f(x)=1,也就是以它结尾的LIS就是他自己,长度为1

可以得出f[0]=1,f[1]=1,f[2]=2,f[3]=3,f[4]=4,f[5]=3

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package test;

import java.util.*;

/**
 * 给定数组arr,设长度为n,输出arr的最长递增子序列。(如果有多个答案,请输出其中字典序最小的)
 * 示例:
 * 输入:[1,2,8,6,4]
 * 返回值:[1,2,4]
 * 说明:其最长递增子序列有3个,(1,2,8)、(1,2,6)、(1,2,4)其中第三个字典序最小,故答案为(1,2,4)
 */
public class LIS {
    /**
     * 最长上升序列,索引x,以s[x]结尾的最长上升序列
     */
    private List<Integer>[] lis;
    /**
     * 原始序列
     */
    private int[] s;
    /**
     * 最长子序列长度,索引x,以s[x]结尾的LIS长度
     */
    private int[] f;

    public LIS(int[] arr) {
        s = arr;
        f = new int[arr.length];
        lis = new ArrayList[s.length];
        // 初始化,假设f[i]长度1也即以f[i]结尾的LIS仅包括自己
        Arrays.fill(f, 1);
        for (int i = 0; i < arr.length; i++) {
            lis[i] = new ArrayList<>();
            lis[i].add(s[i]); // 假设以s[i]结尾的LIS仅包含自己
        }
    }

    private void processLIS() {
        // 最长子序列长度,索引i,以s[i]结尾的LIS长度
        for (int i = 0; i < s.length; i++) {
            // 如果存在j < i 并且 s[j] < i 那么f[i] = max{1, f[j]+1}
            for (int j = 0; j < i; j++) {
                // 切记使用f[i] <= f[j] + 1,因为可能存在诸如2568,1348这种情况,长度一样时需要按字典序过滤
                if (s[j] < s[i] && f[i] <= f[j] + 1) { // 有以f[i]结尾,从f[j]路线抵达的LIS替换原先的LIS
                    // 处理f[i]
                    f[i] = f[j] + 1;
                    // 防止出现以同一个元素结尾的LIS有多个,例如 139和259 都是以9结尾的长度为3的LIS,为保证以arr[i]结尾的LIS只有一个,在此处直接用字典排序过滤
                    List<Integer> tmp = new ArrayList<>();
                    tmp.addAll(lis[j]);
                    tmp.add(s[i]);
                    if(tmp.size() > lis[i].size()) {
                        lis[i] = tmp;
                    } else if(tmp.size() == lis[i].size()) {
                        lis[i] = filterByOrder(tmp, lis[i]);
                    } else {
                        throw new RuntimeException("error processLIS 1");
                    }
                }
            }
        }
    }

    public int getLISMaxLength() {
        processLIS();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < f.length; i++) {
            max = Math.max(max, f[i]);
        }
        return max;
    }

    public List<Integer> getLIS() {
        List<Integer> res = null;
        int maxLength = getLISMaxLength();
        for (int i = 0; i < f.length; i++) {
            if (maxLength == f[i]) {
                if (res == null) {
                    res = lis[i];
                } else {
                    // 说明出现不止一个LIS,需要按字典序过滤
                    res = filterByOrder(res, lis[i]);
                }
            }
        }
        return res;
    }

    /**
     * 返回字典序较小的LIS
     * @param lis1
     * @param lis2
     * @return
     */
    private List<Integer> filterByOrder(List<Integer> lis1, List<Integer> lis2) {
        if(lis1.size() != lis2.size()) {
            throw new RuntimeException("error filterByOrder");
        }
        for(int i = 0; i < lis1.size(); i++) {
            if(lis1.get(i) == lis2.get(i)) {
                continue;
            } else if(lis1.get(i) > lis2.get(i)) {
                return lis2;
            } else {
                return lis1;
            }
        }
        throw new RuntimeException("error filterByOrder,no result");
    }


    public static void main(String[] args) {
        // 25689 13489
        int arr[] = {2,1,5,3,6,4,8,9,7};
        LIS lis = new LIS(arr);
        System.out.println(lis.getLIS());
    }
}
// 运行结果
[1, 2, 4]