字节笔试

public class 翻转子数组后的最大子段和 {
    static long MIN = -(Long.MAX_VALUE >> 20);

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }

        // 以k结尾的最大字段和 + 后半段的最大后缀和
        // 多余的部分可以认为通过翻转被删掉
        //  nums[0~k~n-1]
        //  0 1 2 ... l...k....r r+1 ..... n-1
        //   k+1~r可以认为被删除了 r+1~n-1重新续上sum[k]
        // dp[j]表示从右开始的最大后缀和

        // 复杂度分析
        // 找前半段是的字段和 O(N) + 后半段以O(1)找到最大后缀
        // 总复杂度O(N)
        long[] dp = new long[n + 1];
        long sum = 0, max = MIN;
        dp[n] = MIN;
        for (int j = n - 1; j >= 0; j--) {
            sum += nums[j];
            dp[j] = Math.max(sum, dp[j + 1]);
        }
        sum = 0;
        long res = MIN;
        dp[n] = 0;
        for (int i = 0; i < n; i++) {
                 // fixed 修复最大子段和
            sum =  Math.max(sum + nums[i], nums[i]);
            max = Math.max(max, sum);
            res = Math.max(res, max + dp[i + 1]);
        }
        System.out.println(res);

    }
}

public class 长为k的子数组最大和 {
    /**
     *  可以在n个元素的数组中去掉一个元素
     *  求长为k的子数组的最大和
     *  输入：
     *  5 3
     *  2 1 3 -1 4
     *  输出：
     *  8
     *  解释：去掉-1后  {1, 3, 4}组成k=3的子数组和最大 8
     */
    public static void main(String[] args) {
        // 基本思路就是滑动窗口+单调队列
        // 单调队列维护窗口 最小值的索引
        // 淘汰最小值之后 找到窗口两端相邻的元素补进来
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        ArrayDeque<Integer> q = new ArrayDeque<>(k + 1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // 窗口现成 左端滑出 sum减掉
            if (i >= k) {
                sum -= nums[i - k];
            }
            sum += nums[i];
            while (!q.isEmpty() && nums[i] <= nums[q.peekLast()])
                q.removeLast();
            q.offer(i);

            // 如果对头已经滑出窗口 淘汰
            if (!q.isEmpty() && i - q.peekFirst() + 1 > k) {
                q.removeFirst();
            }
            // 形成了k大小的窗口
            if (i >= k - 1) {
                int x, y = 0, z = 0;
                assert !q.isEmpty();
                x = nums[q.peekFirst()];
                if (i + 1 < nums.length) {
                    y = nums[i + 1];
                }
                if (i >= k)
                    z = nums[i - k];
                // 把窗口内最小元素淘汰 用相邻更大价值的补回来 不然相当于当前窗口不删除元素就已经最大
                res = sum - x + Math.max(Math.max(x, y), z);
            }
        }
        System.out.println(res);

    }
}