ผลรวมสูงสุดของสอง Subarrays ที่ไม่ทับซ้อนกันใน C++

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• กำหนดอาร์เรย์ leftL ขนาด n กำหนดอาร์เรย์ leftM ขนาด n

• กำหนดอาร์เรย์ rightL ขนาด n กำหนดอาร์เรย์ rightM ขนาด n

• ret :=0, temp :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • อุณหภูมิ =อุณหภูมิ + A[i]

• สำหรับการเริ่มต้น i :=L, j :=0, เมื่อ i

  • leftL[i − 1] :=สูงสุดของอุณหภูมิและ x โดยที่ x เป็น 0 เมื่อ i − 2 <0 มิฉะนั้น x =leftL[i − 2]

  • อุณหภูมิ =อุณหภูมิ + A[i]

  • อุณหภูมิ =อุณหภูมิ − A[j]

• leftL[n − 1] :=สูงสุดของอุณหภูมิ และ x โดยที่ x เป็น 0 เมื่อ n − 2 <0 มิฉะนั้น x :=leftL[n − 2]

• อุณหภูมิ :=0

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน

  • อุณหภูมิ =อุณหภูมิ + A[i]

• สำหรับการเริ่มต้น i :=M, j :=0, เมื่อ i

  • อุณหภูมิ =อุณหภูมิ + A[i]

  • อุณหภูมิ =อุณหภูมิ - A[j]

• leftM[n − 1] :=สูงสุดของอุณหภูมิและ x เมื่อ x :=0 ถ้า n - 2 <0 มิฉะนั้น x :=leftM[n − 2]

• อุณหภูมิ :=0

• สำหรับการเริ่มต้น i :=n − 1 เมื่อ i> n − 1 − L ลดลง i 1 ทำ −

  • อุณหภูมิ =อุณหภูมิ + A[i]

• สำหรับการเริ่มต้น i :=n − 1 − L, j :=n − 1 เมื่อ i>=0, ลดลง i ทีละ 1, ลด j ทีละ 1, ทำ −

  • rightL[i + 1] :=สูงสุดของอุณหภูมิและ x โดยที่ x เป็น 0 ถ้า i + 2>=n มิฉะนั้น x =rightL[i + 2]

  • อุณหภูมิ =อุณหภูมิ + A[i]

  • อุณหภูมิ =อุณหภูมิ − A[j]

• rightL[0] :=สูงสุดของอุณหภูมิและ rightL[1]

• อุณหภูมิ :=0

• สำหรับการเริ่มต้น i :=n − 1 เมื่อ i> n − 1 − M ให้ลด i ลง 1 ทำ −

  • อุณหภูมิ =อุณหภูมิ + A[i]

• สำหรับการเริ่มต้น i :=n − 1 − M, j :=n − 1 เมื่อ i>=0, ลดลง i ทีละ 1, ลด j ทีละ 1, ทำ −

  • rightM[i + 1] :=สูงสุดของอุณหภูมิและ x โดยที่ x เป็น 0 เมื่อ i + 2>=n มิฉะนั้น x :=rightM[i + 2]

  • อุณหภูมิ =อุณหภูมิ + A[i]

  • อุณหภูมิ =อุณหภูมิ − A[j]

• rightM[0] :=สูงสุดของอุณหภูมิและ 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]

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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