[数据结构与算法]大厂算法反复面试-最长递增子序列

题目

有n个动物重量分别a1，a2，a3…an,

这群动物一起玩叠罗汉游戏

规定从左往右选择动物，每只动物左边动物的总重量不超过自己的重量

返回最多能选多少个动物，求一个高效的算法

比如有7个动物，从左往右重量依次为 1，3，5，7，9，11，21

最多能选5个动物 1，3，5，9，21

注意：

• 实际给定的数组可能是无序的
• 要求从左往右选动物，且不能打乱原始数组

分析

这道题应该怎么做呢？

确定你审清楚了题目意思，这点很重要，不然浪费了磨脑壳，朝着错误的方向努力，什么也不值了

1. 题目没有说给定的数据是有序的
2. 选择的动物不能随便改变原数组顺序
3. 总重量不超过的意思就是 <=

我们一般人考虑问题都是从简单到复杂，以循序渐进的方式进行，所以从选择1个动物开始分析

数组 1， 3， 5， 7， 9， 11， 21

index 0 1 2 3 4 5 6

定义两个数组

len - 能够选择的动物的数量

ends - 最后一只动物选定之后，累计的总重量

选择到第1只

数组长度，也就是动物的数量为 1 len[1]

因为当前就1只，左边没有动物，重量当然不可能超过自己 0 <= 1

算上自己的总重量 ends[1]

选择到第2只 重量3

左边 1 < 3,

动物的数量为 len[1, 2]

累计重量 ends[1, 4]

选择到第3只 重量5

左边 1 + 3 < 5

动物数量 len [1， 2， 3]

累计重量 4 + 5 = 9 ends[1, 4, 9]

选择到第4只 重量7

左边9 > 7

所以左边 累计重量应该选4合适 4 + 7 = 11 累计重量为11

动物数量继续保持在3 len[1， 2， 3， 3]，

选择1， 3， 7， 累计重量 11 是否合适

1，3，7累计重量11， 1， 3， 5累计重量9，都是3只动物，

但是 9 比 11更合适，因为9更小，后面可以累加的动物数量更多

动物数量 len[1， 2， 3， 3]

累计重量 ends[1， 4， 9, 跳过] 第4只动物就会被跳过

选择到第5只 重量9

左边9 <= 9

动物数量 len[1， 2， 3， 3， 4]

累计重量 ends[1， 4， 9， 跳过， 18]

选择到第6只 重量11

左边 18 > 11

所以左边累计重量应该选9合适 9 + 11 = 20, 累计重量20

动物数量继续保持在4 len[1， 2， 3， 3， 4， 4]，

选择1， 3， 5， 11， 累计重量 20是否合适

1，3，5，9累计重量18， 1，3，5，11 累计重量20， 都是4只动物，

但是 18 比 20更合适，因为18更小，后面可以累加的动物数量更多

动物数量 len[1，2，3，3，4，4]
累计重量 ends[1，4，9，条狗，18，跳过]

选择到第7只 重量21

左边 18 < 21

动物数量 len[1，2， 3，3， 4， 4， 5]

累计重量 ends[1，4，9， 跳过， 18， 跳过， 39]

最终索引到最后一只动物， 动物数量为5只

累计重量数组 ends[1，4，9， 跳过， 18， 跳过， 39]

最终纳入的动物为 1， 3， 5， 9， 21

实现

public class Algorithm0001 {

//    有n个动物重量分别a1，a2，a3....an,
//
//    这群动物一起玩叠罗汉游戏
//
//    规定从左往右选择动物，每只动物左边动物的总重量不超过自己的重量
//
//    返回最多能选多少个动物，求一个高效的算法
//
//    比如有7个动物，从左往右重量依次为 1，3，5，7，9，11，21
//
//    最多能选5个动物 1，3，5，9，21
//
//    注意：
//
//            - 实际给定的数组可能是无序的
//            - 要求从左往右选动物，且不能打乱原始数组

    public static int[] maxAnimal(int[] srcArray) {
        int index = 0; // 按顺序从第一个动物开始

        // 存储累计重量
        int[] ends = new int[srcArray.length];

        // 存储纳入的动物重量
        int[] valids = new int[srcArray.length];
        // 纳入的动物数量
        int validCount = 0;

        // 0- index, 1-validCount
        int[] opt = new int[2];
        opt[0] = index;
        opt[1] = validCount;

        conquer(srcArray, valids, ends, opt);

        index = opt[0];
        validCount = opt[1];
        int[] mArray = new int[validCount];
        for (int i = 0; i < validCount; i++) {
            mArray[i] = valids[i];
        }
        return mArray;
    }

    public static void conquer(int[] srcArray, int[] valids, int[] ends, int[] opt) {
        int index = opt[0];
        int validCount = opt[1];
        if (index < srcArray.length) {
            if (index == 0) {
                valids[validCount] = srcArray[index];
                ends[validCount] = srcArray[index];
                validCount++;

            } else {
                if (ends[validCount - 1] <= srcArray[index]) {
                    valids[validCount] = srcArray[index];
                    ends[validCount] = ends[validCount - 1] + srcArray[index];
                    validCount++;

                } else if (ends[validCount - 1] > srcArray[index]) {
                    if (validCount >= 2) {
                        // 比较累计重量数组 倒数第二项的累计重量+当前索引的动物重量 与 最后一项累计重量 的大小
                        if (ends[validCount - 1] > ends[validCount - 2] + srcArray[index]) {
                            // 说明 当前索引的动物 与 当前已纳入的最后一只动物 相比， 替换已纳入的最后一只动物 更好
                            valids[validCount - 1] = srcArray[index];
                            ends[validCount - 1] = ends[validCount - 2] + srcArray[index];
                        }
                        // else 说明 当前索引的动物 与 当前已纳入的最后一只动物 相比， 保持当前 已纳入的动物 更好， 继续索引下一只
                    } else {
                        // 当前只有1只动物纳入， 但是当前索引的动物重量 比 已纳入的唯一动物重量 小，应该把小的重量的动物纳入，替换掉原来的
                        valids[validCount - 1] = srcArray[index];
                        ends[validCount - 1] = srcArray[index];
                    }
                }
            }
            opt[0] = ++index;
            opt[1] = validCount;
            conquer(srcArray, valids, ends, opt);
        }
    }

    public static void main(String[] args) {
        int n = 1000;
        // 随机一些数
        List<Integer> mArrayList = new ArrayList();
        for (int i = 0; i < n; i++) {
            mArrayList.add((int) (Math.random() * 2 * n) + 1);
        }
        mArrayList.sort(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return (Integer) o1 - (Integer) o2;
            }
        });
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = mArrayList.get(i);
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print("  ");
            if (i % 10 == 0 && i > 0) {
                System.out.print("\n");
            }
        }

        System.out.print("\n");
        System.out.print("\n");

        int[] mArray = maxAnimal(array);
        for (int i = 0; i < mArray.length; i++) {
            System.out.print(mArray[i]);
            System.out.print("  ");
            if (i % 10 == 0 && i > 0) {
                System.out.print("\n");
            }
        }
    }
}