Tổng trung bình lớn nhất trong C ++

Giả sử chúng ta phân chia một hàng số A thành nhiều nhất K nhóm liền kề, sau đó chúng ta sẽ đặt điểm là tổng trung bình của mỗi nhóm. Chúng ta phải tìm ra rằng đâu là số điểm lớn nhất mà chúng ta có thể đạt được. Giả sử A =[9,1,2,3,9] và K là 3, thì kết quả sẽ là 20, điều này là do, lựa chọn tốt nhất là phân vùng A thành [9], [1, 2, 3], [9]. Vì vậy, câu trả lời là 9 + (1 + 2 + 3) / 3 + 9 =20. Chúng tôi cũng có thể phân chia A thành [9, 1], [2], [3, 9],

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

• Xác định dp ma trận
• Xác định một phương thức đệ quy Giải quyết (), Phương thức này sẽ nhận mảng A, chỉ mục và k
• if index> =size of A, sau đó trả về 0
• nếu k bằng 0, thì trả về -100000
• nếu dp [index, k] không phải - 1, thì trả về dp [index, k]
• ret:=-inf và sum:=0
• đối với tôi trong chỉ mục phạm vi đến kích thước là A - 1
  • sum:=sum + A [i]
  • ret:=max của ret và sum / (i - index + 1) + giải (A, i + 1, k - 1)
• đặt dp [index, k]:=ret và return.
• Từ phương pháp chính, hãy thực hiện như sau -
• n:=kích thước của A
• dp:=a ma trận n x (K + 1), điền nó bằng - 1
• trả về giải quyết (A, 0, K)

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

Đầu vào

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

Đầu ra

20