สมมติว่าเรามีอาร์เรย์ 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
กำหนดอาร์เรย์ leftL ขนาด n, อาร์เรย์ leftM ขนาด n
กำหนดอาร์เรย์ rightL ขนาด n, อาร์เรย์ rightM ขนาด n
ret := 0, temp := 0
ลูป i จาก 0 ถึง L-1: temp = temp + A[i]
ลูป i จาก L ถึง n-1, j จาก 0: 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
ลูป i จาก 0 ถึง M-1: temp += A[i]
ลูป i จาก M ถึง n-1, j จาก 0: 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]))
temp := 0
ลูป i จาก n-1 ถึง n-L: temp += A[i]
ลูป i จาก n-1-L ถึง 0, j จาก n-1: 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
ลูป i จาก n-1 ถึง n-M: temp += A[i]
ลูป i จาก n-1-M ถึง 0, j จาก n-1: rightM[i+1] := max(temp, (i+2 >= n ? 0 : rightM[i+2])); temp += A[i]; temp -= A[j]
rightM[0] := max(temp, rightM[1])
ลูป i จาก L-1 ถึง n-1-M: ret := max(ret, leftL[i] + rightM[i+1])
ลูป i จาก M-1 ถึง n-1-L: ret := max(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]); 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
