資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢和最大的k個不相交子列表
假設我們有一個名為nums的數字列表，以及另一個值k，我們需要找到k個不相交的、非空的子列表，使得它們的和的總和最大。我們可以認為k小於或等於nums的大小。
因此，如果輸入類似於nums = [11, -1, 2, 1, 6, -24, 11, -9, 6]，k = 3，則輸出將為36，因為我們可以選擇子列表[11, -1, 2, 1, 6]、[11]和[6]，得到和[19, 11, 6] = 36。
為了解決這個問題，我們將遵循以下步驟：
- n := nums的大小
- 如果n等於0或k等於0，則：
- 返回0
- 定義一個大小為k + 1的陣列hi，並用-inf填充。
- 定義另一個大小為k + 1的陣列open，並用-inf填充。
- hi[0] := 0
- 對於nums中的每個數字：
- 定義一個大小為k + 1的陣列nopen，並用-inf填充。
- 從i := 1初始化，當i <= k時，更新（增加i）：
- 如果open[i] > -inf，則：
- nopen[i] := open[i] + num
- 如果hi[i - 1] > -inf，則：
- nopen[i] := nopen[i]和hi[i - 1] + num的最大值
- 如果open[i] > -inf，則：
- open := 移動(nopen)
- 從i := 1初始化，當i <= k時，更新（增加i）：
- hi[i] := hi[i]和open[i]的最大值
- 返回hi[k]
示例（C++）
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0 || k == 0)
return 0;
vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
hi[0] = 0;
for (int num : nums) {
vector<int> nopen(k + 1, INT_MIN);
for (int i = 1; i <= k; ++i) {
if (open[i] > INT_MIN)
nopen[i] = open[i] + num;
if (hi[i - 1] > INT_MIN)
nopen[i] = max(nopen[i], hi[i - 1] + num);
}
open = move(nopen);
for (int i = 1; i <= k; ++i)
hi[i] = max(hi[i], open[i]);
}
return hi[k];
}
int main(){
vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
int k = 3;
cout << solve(v, 3);
}輸入
{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3輸出
36
更新於： 2020年12月12日
156 次檢視
廣告