C++에서 평균의 최대 합

<시간/>

숫자 A의 행을 최대 K개의 인접 그룹으로 분할한다고 가정하고 점수를 각 그룹의 평균 합계로 설정합니다. 우리는 우리가 달성할 수 있는 가장 큰 점수가 무엇인지 찾아야 합니다. A =[9,1,2,3,9]이고 K가 3이라고 가정하면 결과는 20이 됩니다. 가장 좋은 선택은 A를 [9], [1, 2, 3]으로 분할하는 것이기 때문입니다. [9]. 따라서 답은 9 + (1 + 2 + 3) / 3 + 9 =20입니다. A를 [9, 1], [2], [3, 9],

로 분할할 수도 있습니다.

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

행렬 dp 정의
재귀적 메서드 solve() 정의, 이것은 배열 A, 인덱스 및 k를 사용합니다.
인덱스>=A의 크기이면 0을 반환합니다.
k가 0이면 -100000을 반환합니다.
dp[index, k]가 – 1이 아니면 dp[index, k]를 반환
ret :=-inf 및 합계 :=0
A 크기에 대한 범위 인덱스의 i에 대해 - 1
- 합계 :=합 + A[i]
- ret :=ret 및 sum의 최대값/(i – 인덱스 + 1) + solve(A, i + 1, k – 1)
dp[index, k] 설정 :=ret 및 반환.
메인 방법에서 다음을 수행하십시오. -
n :=A의 크기
dp :=행렬 n x (K + 1), – 1로 채움
반환 풀기(A, 0, K)

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector < vector <double> > dp;
   double solve(vector <int>& A, int idx, int k){
      if(idx >= A.size()) return 0;
      if(!k) return -100000;
      if(dp[idx][k] != -1) return dp[idx][k];
      double ret = INT_MIN;
      double sum = 0;
      for(int i = idx; i < A.size(); i++){
         sum += A[i];
         ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
      }
      return dp[idx][k] = ret;
   }
   double largestSumOfAverages(vector<int>& A, int K) {
      int n = A.size();
      dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
      return solve(A, 0, K);
   }
};
main(){
   vector<int> v = {9,1,2,3,9};
   Solution ob;
   cout << (ob.largestSumOfAverages(v, 3));
}

입력

[9,1,2,3,9]
3

C++에서 평균의 최대 합

예시

입력

출력