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

相关文章

来自专栏nnngu

Hibernate的继承映射

对象模型示例: ? 继承映射的实现方式有以下三种: (一)每棵类继承树一张表 (二)每个类一张表 (三)每个子类一张表 (一)每棵类继承树一张表 关系模型如下:...

2624
来自专栏北京马哥教育

Python有趣的小案例

5994
来自专栏清墨_iOS分享

OpenGLES-02 绘制基本图元(点、线、三角形)

在绘制之前,我们需要了解下面的知识: 一、渲染管线 下图中展示整个OpenGL ES 2.0可编程渲染管线 ? 渲染管线.png 图中Vertex Shade...

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

C语言程序设计50例(一)(经典收藏)

【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组...

3517
来自专栏田云专栏

virtualdom diff算法实现分析

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现,记录下学习心得。

2806
来自专栏mySoul

C++ 面向对象 一

使用内联函数的时候,编译器会进行自动替换,即类似于C语言中的宏。以减少入栈和出栈的操作。

793
来自专栏IT开发技术与工作效率

公式流程图时序图.md 测试

1323
来自专栏我是业余自学C/C++的

Search in Rotated Sorted Array II

Follow up forSearch in Rotated Sorted Array :What if duplicates are allowed?

793
来自专栏未闻Code

使用有限状态机原理实现英文分词

使用Python开发一个英文句子分词程序,把一段英文句子切分为每一个单词。不能导入任何官方的或者第三方的库,也不能使用字符串的split()方法。

691
来自专栏数据结构与算法

P2733 家的范围 Home on the Range

题目背景 农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。(因为一些原因,他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的...

2735

扫码关注云+社区