算法

    public int lengthOfLIS(int[] nums) {
        // 初始化dp数组为1
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int maxEnvelopes (int[][] envelopes) {
        int n = envelopes.length;
        // 重写排序规则
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 按照第一个元素递增、相同情况下第二个元素递减排序
                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
            }
        });

        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            // 第一个元素有序，第二个元素无序，寻找最长递增子序列
            height[i] = envelopes[i][1];
        }
        return lengthOfLIS(height);
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];

        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            // 即使有负数也不影响，新的正数发现补不回前面的缺口就会断尾
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int dp_0 = nums[0];
        // 化数组为两个数滚动
        int dp_1 = 0;
        int res = dp_0;

        for (int i = 1; i < n; i++) {
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;
            // 直接比较减少循环
            res = Math.max(res, dp_1);
        }
        
        return res;
    }