資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中分割陣列最大和
假設我們有一個正整數陣列和一個值 m。我們可以將此陣列分成 m 個連續的子陣列。我們必須設計一種演算法來最小化這 m 個子陣列中最大的和。
所以如果陣列是 [7,2,4,10,9]，並且 m = 2，那麼和將是 19，因為我們可以建立兩個子陣列，如 [7,2,4] 和 [10,9]，然後子陣列的最大和是 19。
為了解決這個問題，我們將遵循以下步驟 -
- 定義一個函式 splitArray()，它將接收一個數組 v、m，
- n := v 的大小
- 建立一個大小為 的 dp 陣列
- 建立一個大小為 n 的 sum 陣列
- sum[0] := v[0]
- 初始化 i := 1，當 i < n 時，更新（i 增加 1），執行 -
- sum[i] := sum[i - 1] + v[i]
- dp[0] := sum[n - 1]
- 初始化 i := 1，當 i < n 時，更新（i 增加 1），執行 -
- dp[i] := sum[n - 1] - sum[i - 1]
- 初始化 i := 1，當 i < m 時，更新（i 增加 1），執行 -
- 初始化 start := 0，當 start < n - i 時，更新（start 增加 1），執行 -
- 初始化 end := start + 1，當 end <= n - i 時，更新（end 增加 1），執行 -
- dp[start] := dp[start] 和 (當 start 為 0 時 sum[end - 1]，否則 sum[end - 1] - sum[start - 1]) 和 dp[end] 的最小值
- 初始化 start := 0，當 start < n - i 時，更新（start 增加 1），執行 -
- 返回 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
輸出
19
更新於: 2020-06-01
332 次檢視
廣告