C++에서 배열 최대 합 분할

<시간/>

양의 정수 배열과 하나의 값 m이 있다고 가정합니다. 이 배열을 m개의 연속적인 하위 배열로 나눌 수 있습니다. 이 m개의 하위 배열 중에서 가장 큰 합을 최소화하는 알고리즘을 고안해야 합니다.

따라서 배열이 [7,2,4,10,9]이고 m =2인 경우 [7,2,4] 및 [10,9]와 같은 두 개의 하위 배열을 만들 수 있으므로 합계는 19가 됩니다. , 합계가 가장 큰 부분배열은 19입니다.

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

splitArray() 함수를 정의하면 배열 v, m,
n :=v의 크기
하나의 배열 dp 크기 만들기
크기가 n인 다른 배열의 합을 만듭니다.
합[0] :=v[0]
초기화 i :=1의 경우, i
합[i] :=합[i - 1] + v[i]

dp[0] :=합계[n - 1]

초기화 i :=1의 경우, i

dp[i] :=합계[n - 1] - 합계[i - 1]

초기화 i:=1의 경우, i

초기화 시작의 경우:=0, 시작

초기화 종료의 경우:=시작 + 1, 종료 <=n - i일 때 업데이트(끝을 1씩 증가), −

dp[start] :=dp[start]의 최소값과 (start가 0일 때 sum[end - 1], 그렇지 않으면 sum[end - 1] - sum[start - 1]) 및 dp[end]의 최대값

반환 dp[0]

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

예

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int splitArray(vector<int>& v, int m) {
      int n = v.size();
      vector <long long int > dp(n);
      vector <long long int> sum(n);
      sum[0] = v[0];
      for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
      dp[0] = sum[n-1];
      for(int i =1;i<n;i++){
         dp[i] = sum[n-1] - sum[i-1];
      }
      for(int i =1;i<m;i++){
         for(int start = 0;start<n-i;start++){
            for(int end = start+1;end<=n-i;end++){
               dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
            }
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<int> v = {7,2,4,10,9};
   cout << (ob.splitArray(v, 2));
}

입력

[7,2,4,10,9]
2

C++에서 배열 최대 합 분할

예

입력

출력