621. 最大子序列

描述

给定一个整数数组，找到长度在 k1 与 k2 之间(包括 k1, k2)的子序列并且使它们的和最大，返回这个最大值，如果数组元素个数小于 k1 则返回 0

注意事项

确保结果是一个整型

样例

给定一个数组 [-2,2,-3,4,-1,2,1,-5,3]，k1 = 2，k2 = 4，连续子序列为 [4,-1,2,1] 时有最大和 6

代码

public class Solution {
    /**
     * @param nums an array of integers
     * @param k1 an integer
     * @param k2 an integer
     * @return the largest sum
     */
    public int maxSubarray5(int[] nums, int k1, int k2) {
        int n = nums.length;
        if (n < k1) {
            return 0;
        }

        int result = Integer.MIN_VALUE;

        int[] sum = new int[n + 1];
        sum[0] = 0;
        // 链表中存储的是前缀和下标且对应前缀和升序排列
        LinkedList<Integer> queue = new LinkedList<Integer>();

        for (int i = 1; i <= n; ++i) {
            // sum 代表前 n 个数的和
            sum[i] = sum[i - 1] + nums[i - 1];

            // 队列非空且链表的第一个下标小于 i-k2
            // k2 是子序列的的最长长度，i-k2 代表 queue 中有意义的前缀和最小下标
            if (!queue.isEmpty() && queue.getFirst() < i - k2) {
                queue.removeFirst();
            }
            if (i >= k1) {
                // i-k1 代表最后一个有意义的前缀和最大下标
                // 要求到最大的连续序列和，我们要求前缀和最小，保留更小的前缀和
                // 每加入一个新的下标，要将所有前缀和比它大的下标全部删掉
                // 注意此处是 while 循环
                while (!queue.isEmpty() && sum[queue.getLast()] > sum[i - k1]) {
                    queue.removeLast();
                }
                // i > k1 的特判主要在这一步起作用，往队列中加入的 sum 数组的前缀和下标不能是负数
                queue.add(i - k1);
            }

            // 所有下标值都在 [i - k2, i - k1] 之间，并且对应的 sum 数组中的值按降序排列
            // 每增长一个 i， i - k2 的值都在增长，必然会将上一次操作的 queue.getFirst() 淘汰，这样也就在 for 循环的同时也遍历了队列
            if (!queue.isEmpty() && sum[i] - sum[queue.getFirst()] > result) {
                result = Math.max(result, sum[i] - sum[queue.getFirst()]);
            }
        }
        return result;
    }
}