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 条评论
登录 后参与评论

相关文章

来自专栏前端架构

AngularJS API之extend扩展对象

这种使用方式,会保留原始对象,把user1与user2进行整合,在复制给user3.

622
来自专栏漫漫全栈路

JSON学习笔记

JSON学习笔记 Web学习笔记之——Json ---- 什么是JSON JSON: JavaScript Object Notation(JavaScri...

2734
来自专栏前端知识分享

第11天:JS中变量、字符串基础知识

js页面效果:轮播图、选项卡、地图、表单验证javascript是弱变量类型的语言,变量只需要用var来声明。而java要根据变 量类型来声明,

963
来自专栏Java3y

JSP第四篇【EL表达式介绍、获取各类数据、11个内置对象、执行运算、回显数据、自定义函数、fn方法库】

什么是EL表达式? 表达式语言(Expression Language,EL),EL表达式是用"${}"括起来的脚本,用来更方便的读取对象! EL表达式主要用来...

3627
来自专栏GreenLeaves

JS框架设计之对象类型判断一种子模块

Javascript有两套数据类型,一套是基础数据类型,一套是对象数据类型。基础数据类型包括5种基本数据类型,分别是null,bool,undefined,nu...

1808
来自专栏Golang语言社区

【前端基础】JS基础学习笔记整理

JavaScript是一种基于对象的脚本编程语言,是浏览器上的程序语言。当web容器输出内容到浏览器时,这个内容是包含js源代码的,此时,JavaScript可...

3757
来自专栏测试开发架构之路

crontab定时时间解释

用户所建立的crontab文件中,每一行都代表一项任务,每行的每个字段代表一项设置,它的格式共分为六个字段,前五段是时间设定段,第六段是要执行的命令段,格式如下...

683
来自专栏IMWeb前端团队

JavaScript强化教程——保留关键字

本文作者:IMWeb 王军 原文出处:IMWeb社区 未经同意,禁止转载 本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScr...

1886
来自专栏mathor

C语言有参数宏定义与无参数宏定义

803
来自专栏noteless

XML概念定义以及如何定义xml文件编写约束条件java解析xml DTD XML Schema JAXP java xml解析 dom4j 解析 xpath dom sax

本文主要涉及:xml概念描述,xml的约束文件,dtd,xsd文件的定义使用,如何在xml中引用xsd文件,如何使用java解析xml,解析xml方式dom s...

683

扫码关注云+社区