大兔崽子

# 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

### 大兔崽子

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】

06/13
0
0
LeetCode 974 Subarray Sums Divisible by K

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

19分钟前
5
0
Spring Boot 2.x基础教程：Swagger静态文档的生成

23分钟前
4
0
《毅力》读书笔记

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

lingch
24分钟前
3
0

27分钟前
3
0

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

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