C++에서 3개의 비중첩 부분배열의 최대 합

nums of positive integers라고 하는 하나의 배열이 있다고 가정하고 최대 합계를 가진 3개의 겹치지 않는 하위 배열을 찾아야 합니다. 여기서 각 하위 배열의 크기는 k이고 모든 3*k 항목의 합계를 최대화하려고 합니다.

각 구간의 시작 위치를 나타내는 인덱스 목록으로 결과를 찾아야 합니다. 답변이 여러 개인 경우 사전순으로 가장 작은 답변을 반환합니다.

따라서 입력이 [1,2,1,2,6,8,4,1]이고 k =2이면 결과는 [0,3,5]이므로 하위 배열은 [1,2]입니다. [2,6], [8,4]는 시작 인덱스 [0,3,5]에 해당합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=숫자 크기
• 크기가 3인 배열 ret를 정의하고 inf로 채웁니다.
• n + 1 크기의 배열 합계 정의
• 초기화 i의 경우:=0, i
• 합[i + 1] =합[i] + 숫자[i]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

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

출력

[0, 3, 5, ]