LWC 52:689. Maximum Sum of 3 Non-Overlapping Subarrays

LWC 52:689. Maximum Sum of 3 Non-Overlapping Subarrays

传送门:689. Maximum Sum of 3 Non-Overlapping Subarrays

Problem:

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size k, and we want to maximize the sum of all 3*k entries. Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

nums.length will be between 1 and 20000.

nums[i] will be between 1 and 65535.

k will be between 1 and floor(nums.length / 3).

思路: dp[i]:表示从i下标开始,长度为k的subArray的和。dp[i] = nums[i] + nums[i+1]+...+nums[i+k-1],这样给定当前坐标i,只需要求出位于左侧的最大max{dp[i'] | i' <= i - k}记录之,同理求出右侧的最大max{dp[j] | j >= i + k}

代码如下:

    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        // 累加和,区间计算时,只需O(1)
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = nums[i] + sum[i]; 
        }

        int[] dp = new int[n];

        // 对应最后一个区间的选择范围
        for (int l = 2 * k; l + k <= n; ++l) {
            dp[l] = sum[l + k] - sum[l];
        }

        // 对应第二个区间的选择范围
        for (int l = k; l + 2 * k <= n; ++l) {
            dp[l] = sum[l + k] - sum[l];
        }

        // 对应第一个区间的选择范围
        for (int l = 0; l + 3 * k <= n; ++l) {
            dp[l] = sum[l + k] - sum[l];
        }

        // 记录当前i下,符合i' <= i - k的dp[i']中最大下标
        int[] left = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i - k >= 0) {
                if (left[i - 1] == -1) {
                    left[i] = i - k;
                }
                else if (dp[i - k] <= dp[left[i - 1]]) {
                    left[i] = left[i - 1];
                }
                else{
                    left[i] = i - k;
                }
            }
            else {
                left[i] = -1; //表示当前i的左侧没有合法的i'
            }
        }

        // 记录当前i下,符合j >= i + k的dp[j]中最大下标
        int[] right = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            if (i + k < n) {
                if (right[i + 1] == -1) {
                    right[i] = i + k;
                }
                else if (dp[right[i + 1]] > dp[i + k]) {
                    right[i] = right[i + 1];
                }
                else {
                    right[i] = i + k;
                }
            }
            else {
                right[i] = -1; //表示当前i的右侧没有合法的j
            }
        }

        int max = 0;
        int[] res = {-1, -1, -1};
        for (int i = 0; i < n; ++i) {
            if (left[i] != -1 && right[i] != -1) {
                int tmp = dp[i] + dp[right[i]] + dp[left[i]];
                if (tmp > max) {
                    max = dp[i] + dp[right[i]] + dp[left[i]];
                    res[0] = left[i];
                    res[1] = i;
                    res[2] = right[i];
                }
            }
        }
        return res;
    }

注意求解left和right中选取最大值的if判断,一个有等号,一个无等号,是为了 return the lexicographically smallest one.

精简版本:

    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = nums[i] + sum[i]; 
        }

        int[] dp = new int[n];

        for (int i = 0; i + k <= n; ++i){
            dp[i] = sum[i + k] - sum[i];
        }

        int[] left = new int[n];
        Arrays.fill(left, -1);
        for (int i = k; i < n; ++i) {
            if (i - k == 0 || dp[i - k] > dp[left[i - 1]]) {
                left[i] = i - k;
            }
            else {
                left[i] = left[i - 1];
            }
        }

        int[] right = new int[n];
        Arrays.fill(right, -1);
        for (int i = n - k - 1; i >= 0; --i) {
            if (i + k == n - 1 || dp[right[i + 1]] <= dp[i + k]){
                right[i] = i + k;    
            }
            else{
                right[i] = right[i + 1];
            }
        }

        int max = 0;
        int[] res = {-1, -1, -1};
        for (int i = 0; i < n; ++i) {
            if (left[i] != -1 && right[i] != -1) {
                int tmp = dp[i] + dp[right[i]] + dp[left[i]];
                if (tmp > max) {
                    max = dp[i] + dp[right[i]] + dp[left[i]];
                    res[0] = left[i];
                    res[1] = i;
                    res[2] = right[i];
                }
            }
        }
        return res;
    }    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Educational Codeforces Round 21 D.Array Division(二分)

D. Array Division time limit per test:2 seconds memory limit per test:256 megaby...

33111
来自专栏大数据挖掘DT机器学习

【知识】SAS学习笔记(1--2)

(1)SAS基本概念 1. SAS数据集 SAS数据集(SAS Datasets)可以看作由若干行和若干列组成的表格,类似于一个矩阵,但各列可以取不同的类型值...

3277
来自专栏计算机视觉与深度学习基础

Leetcode 91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the fol...

1747
来自专栏余林丰

MyBatis之级联——鉴别器

鉴别器(discriminator)是MyBatis为我们提供的第三个级联也是最后一个。基于之前两篇级联中的场景,现增加学生们去体检,但男女体检项目不一样,我们...

2367
来自专栏文渊之博

Hive 时间日期处理总结

最近用hive比较多,虽然效率低,但是由于都是T+1的业务模式。所以也就不要求太多了,够用就行。其中用的吧比较多就是时间了,由于大数据中很多字段都不是标准的时间...

3887
来自专栏小樱的经验随笔

51 Nod 1027 大数乘法【Java大数乱搞】

1027 大数乘法 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 给出2个大整数A,B,计算A*B的结果。 Input 第1行:...

1854
来自专栏xingoo, 一个梦想做发明家的程序员

[翻译]CURAND Libaray--Host API--(2)

2.3 返回值 所有的CURAND host端的函数返回值都是curandStatus_t.如果调用没有错误,则返回成功,即返回值为CURAND_STATUS_...

18910
来自专栏算法channel

算法优化|说说哨兵(sentinel value)

01 哨兵 先看下维基百科对其定义: In computer programming, a sentinel value (also referred to ...

3358
来自专栏LeetCode

LeetCode 34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and...

1124
来自专栏King_3的技术专栏

leetcode-695-Max Area of Island(BFS)

952

扫码关注云+社区