資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中兩個不重疊子陣列的最大和
假設我們有一個整數陣列 A；我們需要找到兩個不重疊子陣列元素的最大和。這兩個子陣列的長度分別為 L 和 M。
更準確地說，我們需要找到最大的 V，其中
V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 並且滿足以下條件之一：
0 <= i < i + L − 1 < j < j + M − 1 < A 的大小，或者
0 <= j < j + M − 1 < i < i + L − 1 < A 的大小。
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小
定義一個大小為 n 的陣列 leftL，定義一個大小為 n 的陣列 leftM
定義一個大小為 n 的陣列 rightL，定義一個大小為 n 的陣列 rightM
ret := 0，temp := 0
初始化 i := 0，當 i < L 時，將 i 增加 1：
temp = temp + A[i]
初始化 i := L，j := 0，當 i < n 時，將 i 增加 1，將 j 增加 1：
leftL[i − 1] := temp 和 x 的最大值，其中 x 為 0（如果 i − 2 < 0），否則 x = leftL[i − 2]
temp = temp + A[i]
temp = temp − A[j]
leftL[n − 1] := temp 和 x 的最大值，其中 x 為 0（如果 n − 2 < 0），否則 x := leftL[n − 2]
temp := 0
初始化 i := 0，當 i < M 時，將 i 增加 1：
temp = temp + A[i]
初始化 i := M，j := 0，當 i < n 時，將 i 增加 1，將 j 增加 1：
temp = temp + A[i]
temp = temp - A[j]
leftM[n − 1] := temp 和 x 的最大值，其中 x := 0（如果 n - 2 < 0），否則 x := leftM[n − 2]
temp := 0
初始化 i := n − 1，當 i > n − 1 − L 時，將 i 減少 1：
temp = temp + A[i]
初始化 i := n − 1 − L，j := n − 1，當 i >= 0 時，將 i 減少 1，將 j 減少 1：
rightL[i + 1] := temp 和 x 的最大值，其中 x 為 0（如果 i + 2 >= n），否則 x = rightL[i + 2]
temp = temp + A[i]
temp = temp − A[j]
rightL[0] := temp 和 rightL[1] 的最大值
temp := 0
初始化 i := n − 1，當 i > n − 1 − M 時，將 i 減少 1：
temp = temp + A[i]
初始化 i := n − 1 − M，j := n − 1，當 i >= 0 時，將 i 減少 1，將 j 減少 1：
rightM[i + 1] := temp 和 x 的最大值，其中 x 為 0（如果 i + 2 >= n），否則 x := rightM[i + 2]
temp = temp + A[i]
temp = temp − A[j]
rightM[0] := temp 和 rightM[1] 的最大值
初始化 i := L − 1，當 i <= n − 1 − M 時，將 i 增加 1：
ret := ret 和 leftL[i] + rightM[i + 1] 的最大值
初始化 i := M − 1，當 i <= n − 1 − L 時，將 i 增加 1：
ret := ret 和 leftM[i] + rightL[i + 1] 的最大值
返回 ret
讓我們看一下下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
int n = A.size();
vector <int> leftL(n);
vector <int> leftM(n);
vector <int> rightL(n);
vector <int> rightM(n);
int ret = 0;
int temp = 0;
for(int i = 0; i < L; i++){
temp += A[i];
}
for(int i = L, j = 0; i < n; i++, j++){
leftL[i − 1] = max(temp, i − 2 < 0 ? 0 : leftL[i − 2]);
temp += A[i];
temp −= A[j];
}
leftL[n − 1] = max(temp, n − 2 < 0 ? 0 : leftL[n − 2]);
temp = 0;
for(int i = 0; i < M; i++){
temp += A[i];
}
for(int i = M, j = 0; i < n; i++, j++){
leftM[i − 1] = max(temp, i − 2 < 0 ? 0 : leftM[i − 2]);
temp += A[i];
temp −= A[j];
}
leftM[n − 1] = max(temp, n − 2 < 0 ? 0 : leftM[n − 2]);
//out(leftM);
temp = 0;
for(int i = n − 1; i > n − 1 − L; i−−){
temp += A[i];
}
for(int i = n − 1 − L, j = n − 1; i >= 0 ; i−−, j−− ){
rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
temp += A[i];
temp −= A[j];
}
rightL[0] = max(temp, rightL[1]);
temp = 0;
for(int i = n − 1; i > n − 1 − M; i−−){
temp += A[i];
}
for(int i = n − 1 − M, j = n − 1; i >= 0 ; i−−, j−− ){
rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
temp += A[i];
temp −= A[j];
}
rightM[0] = max(temp, rightM[1]);
for(int i = L − 1; i <= n − 1 − M; i++){
ret = max(ret, leftL[i] + rightM[i + 1]);
}
for(int i = M − 1; i <= n − 1 − L; i++){
ret = max(ret, leftM[i] + rightL[i + 1]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v1 = {0,6,5,2,3,5,1,9,4};
cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}輸入
[0,6,5,2,3,5,1,9,4] 1 2
輸出
20
182 次瀏覽
