資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
- 如果 index >= A 的大小，則返回 0
- 如果 k 為 0，則返回 -100000
- 如果 dp[index, k] 不為 – 1，則返回 dp[index, k]
- ret := -inf 且 sum := 0
- 對於 i 的範圍從 index 到 A 的大小 – 1
- sum := sum + A[i]
- ret := ret 和 sum/(i – index + 1) + solve(A, i + 1, k – 1) 的最大值
- 設定 dp[index, k] := ret 並返回。
- 從主方法中，執行以下操作 -
- n := A 的大小
- dp := 一個 n x (K + 1) 的矩陣，用 – 1 填充它
- 返回 solve(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
輸出
20
更新於: 2020-05-04
105 次檢視
廣告