文档章节

1031. Maximum Sum of Two Non-Overlapping Subarrays

大兔崽子
 大兔崽子
发布于 05/05 19:07
字数 422
阅读 17
收藏 0

Problem

Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M. (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

0 <= i < i + L - 1 < j < j + M - 1 < A.length, or 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

Solution

Use bruteforce. Calculate the sum of every L-length subarray and M-length subarray and use additional vectors l_sum where l_sum[i] keeps the max sum of L-length subarray in A[0:i], rl_sum where rl_sum[i] keeps the max sum of L-length subarray in A[i:A.length - 1], m_sum(like l_sum) and rm_sum(like rl_sum).

Code

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        int l_sum[1001] = {0}, rl_sum[1001] = {0}, m_sum[1001] = {0}, rm_sum[1001] = {0};
        l_sum[L - 1] = accumulate(A.begin(), A.begin() + L, 0);
        int tmp = l_sum[L - 1];
        for (auto i = L; i < A.size(); i++)
        {
            tmp = tmp - A[i - L] + A[i];
            if (tmp > l_sum[i - 1])
            {
                l_sum[i] = tmp;
            }
            else
            {
                l_sum[i] = l_sum[i - 1];
            }
        }
        rl_sum[A.size() - L] = accumulate(A.end() - L, A.end(), 0);
        tmp = rl_sum[A.size() - L];
        for (int i = A.size() - L - 1; i >= 0; i--)
        {
            tmp = tmp - A[i + L] + A[i];
            if (tmp > rl_sum[i + 1])
            {
                rl_sum[i] = tmp;
            }
            else
            {
                rl_sum[i] = rl_sum[i + 1];
            }
        }
        m_sum[M - 1] = accumulate(A.begin(), A.begin() + M, 0);
        tmp = m_sum[M - 1];
        for (auto i = M; i < A.size(); i++)
        {
            tmp = tmp - A[i - M] + A[i];
            if (tmp > m_sum[i - 1])
            {
                m_sum[i] = tmp;
            }
            else
            {
                m_sum[i] = m_sum[i - 1];
            }
        }
        rm_sum[A.size() - M] = accumulate(A.end() - M, A.end(), 0);
        tmp = rm_sum[A.size() - M];
        for (int i = A.size() - M - 1; i >= 0; i--)
        {
            tmp = tmp - A[i + M] + A[i];
            if (tmp > rm_sum[i + 1])
            {
                rm_sum[i] = tmp;
            }
            else
            {
                rm_sum[i] = rm_sum[i + 1];
            }
        }
        int ret = 0;
        for (auto i = L - 1; i < A.size() - M; i++)
        {
            if (l_sum[i] + rm_sum[i + 1] > ret)
            {
                ret = l_sum[i] + rm_sum[i + 1];
            }
        }
        for (auto i = M - 1; i < A.size() - L; i++)
        {
            if (m_sum[i] + rl_sum[i + 1] > ret)
            {
                ret = m_sum[i] + rl_sum[i + 1];
            }
        }
        return ret;
    }
};

Love u 500

© 著作权归作者所有

大兔崽子
粉丝 1
博文 27
码字总数 24376
作品 0
杭州
私信 提问
Lintcode42 Maximum Subarray II solution 题解

【题目描述】 Given an array of integers, find two non-overlapping subarrays which have the largest sum.The number in each subarray should be contiguous.Return the largest sum. N......

abcdd1234567890
2018/06/29
0
0
Leetcode 【442、1031】

问题描述:【Array】442. Find All Duplicates in an Array 解题思路: 这道题很容易想到用和数组一样大小的空间来统计每个数字出现的次数,然后输出出现次数为 2 的那些数字即可。但是这样时...

牛奶芝麻
06/13
0
0
LeetCode 974 Subarray Sums Divisible by K

题目描述 Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K. Example 1: Note: 代码 半暴力解法(超时) 定义一个s......

被称为L的男人
01/13
0
0
LeetCode 分类刷题 —— Bit Manipulation

Bit Manipulation 的 Tips: 异或的特性。第 136 题,第 268 题,第 389 题,第 421 题, 构造特殊 Mask,将特殊位置放 0 或 1。 有特殊意义的 & 位操作运算。第 260 题,第 201 题,第 318 ...

一缕殇流化隐半边冰霜
07/12
0
0
Atcoder Tenka1 Programmer Beginner Contest IntegerotS 【异或+思维】

IntegerotS Time Limit: 4000/2000 MS (Java/Others) Memory Limit:262144/262144 K (Java/Others) Problem Description Seisu-ya, a store specializing in non-negative integers, sellsN ......

my_sunshine26
2017/10/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可能是国内第一篇全面解读 Java 现状及趋势的文章

作者 | 张晓楠 Dragonwell JDK 最新版本 8.1.1-GA 发布,包括全新特性和更新! 导读:InfoQ 发布《2019 中国 Java 发展趋势报告》,反映 Java 在中国发展的独特性,同时也希望大家对 Java 有...

阿里云官方博客
19分钟前
5
0
Spring Boot 2.x基础教程:Swagger静态文档的生成

前言 通过之前的两篇关于Swagger入门以及具体使用细节的介绍之后,我们已经能够轻松地为Spring MVC的Web项目自动构建出API文档了。如果您还不熟悉这块,可以先阅读: Spring Boot 2.x基础教程...

程序猿DD
23分钟前
4
0
《毅力》读书笔记

1.确信你全身心地投入 2.准备好为目标进行艰难的跋涉 3.通过减少需要使用毅力的情形,为将来的挑战做好准备 4.尽可能具体细致地确定你的目标和实现目标的过程 5.把挑战分解为小而易于管理的小...

lingch
24分钟前
3
0
zk中快速选举FastLeaderElection实现

选举涉及概念 服务器状态 投票 如何选择投票? 协议 选举 如何进行选举? epoch 发送者 接收者 发送队列 接收队列 服务器状态 public enum ServerState { LOOKING,寻找Leader状态,当服务处于...

writeademo
27分钟前
3
0
教你玩转Linux—磁盘管理

Linux磁盘管理好坏直接关系到整个系统的性能问题,Linux磁盘管理常用三个命令为df、du和fdisk。 df df命令参数功能:检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了多少...

Linux就该这么学
29分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部