Tổng tối đa của 3 mảng con không chồng chéo trong C ++

Giả sử chúng ta có một mảng được gọi là nums các số nguyên dương, chúng ta phải tìm ba mảng con không trùng nhau với tổng lớn nhất. Ở đây, mỗi mảng con sẽ có kích thước k và chúng tôi muốn tối đa hóa tổng của tất cả các mục nhập 3 * k.

Chúng ta phải tìm kết quả dưới dạng danh sách các chỉ số đại diện cho vị trí bắt đầu của mỗi khoảng thời gian. Nếu có nhiều câu trả lời, chúng tôi sẽ trả về câu trả lời nhỏ nhất về mặt từ vựng.

Vì vậy, nếu đầu vào giống như [1,2,1,2,6,8,4,1] và k =2, thì kết quả sẽ là [0,3,5], vì vậy các mảng con là [1,2], [2,6], [8,4] tương ứng với các chỉ số bắt đầu [0,3,5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• Xác định ret mảng có kích thước 3, điền vào phần này với inf
• Xác định tổng mảng có kích thước n + 1
• để khởi tạo i:=0, khi i
• sum [i + 1] =sum [i] + nums [i]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
      int n = nums.size();
      vector <int> ret(3, INT_MAX);
      vector <int> sum(n + 1);
      for(int i = 0; i < n; i++){
         sum[i + 1] = sum[i] + nums[i];
      }
      vector <int> posLeft(n);
      vector <int> posRight(n, n - k);
      for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){
         int newTotal = sum[i + 1] - sum[i + 1- k];
         if(newTotal > currMax){
            currMax = newTotal;
            posLeft[i] = i + 1 - k;
         }else{
            posLeft[i] = posLeft[i - 1];
         }
      }
      for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){
         int newTotal = sum[i + k] - sum[i];
         if(newTotal >= currMax){
            currMax = newTotal;
            posRight[i] = i;
         }else{
            posRight[i] = posRight[i + 1];
         }
      }
      int req = 0;
      for(int i = k; i <= n - 2 * k; i++){
         int l = posLeft[i - 1];
         int r = posRight[i + k];
         int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);
         if(temp > req){
            ret[0] = l;
            ret[1] = i;
            ret[2] = r;
            req = temp;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,2,6,8,4,1};
   print_vector(ob.maxSumOfThreeSubarrays(v, 2));
}

Đầu vào

{1,2,1,2,6,8,4,1}
2

Đầu ra

[0, 3, 5, ]