資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++陣列最大平均和分割槽
問題陳述
給定一個數組，我們將一行數字A最多劃分為K個相鄰的（非空）組，則分數是每個組平均值的總和。可以獲得的最大分數是多少？
示例
如果輸入陣列是{9, 2, 5, 3, 10}，則我們可以如下劃分陣列：
{9} {2, 5, 3} 和 {10}，則平均和為：
9 + (2 + 5 + 3)/ 3 + 10 = 22.33
演算法
我們可以使用記憶化技術來解決這個問題：
- 令memo[i][k]為將A[i到n-1]最多劃分為K部分的最佳分數
- 在第一組中，我們將A[i到n-1]劃分為A[i到j-1]和A[j到n-1]，則我們的候選分割槽的分數為average(i, j) + score(j, k-1))，其中average(i, j) = (A[i] + A[i+1] + … + A[j-1]) / (j – i)。我們取這些分數中的最高分。
- 總的來說，我們的一般情況下的遞迴是：memo[n][k] = max(memo[n][k], score(memo, i, A, k-1) + average(i, j))
示例
讓我們來看一個例子：
#include <bits/stdc++.h>
using namespace std;
define MAX 1000
double memo[MAX][MAX];
double score(int n, vector<int>& arr, int k) {
if (memo[n][k] > 0) {
return memo[n][k];
}
double sum = 0;
for (int i = n - 1; i > 0; i--) {
sum += arr[i];
memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
}
return memo[n][k];
}
double getLargestSum(vector<int>& arr, int K) {
int n = arr.size();
double sum = 0;
memset(memo, 0.0, sizeof(memo));
for (int i = 0; i < n; i++) {
sum += arr[i];
memo[i + 1][1] = sum / (i + 1);
}
return score(n, arr, K);
}
int main() {
vector<int> arr = {9, 2, 5, 3, 10}; int K = 3;
cout << "Largest sum = " << getLargestSum(arr, K) << endl;
return 0;
}輸出
編譯並執行上述程式後，將生成以下輸出：
Largest sum = 22.3333
更新於：2019年12月31日
瀏覽量：157
廣告