資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的受約束子序列和
假設我們有一個名為 nums 的陣列和一個整數 k，我們需要找到該陣列的非空子序列的最大和，使得對於子序列中每兩個連續的數字 nums[i] 和 nums[j]，其中 i < j，條件 j - i <= k 為真。
眾所周知，陣列的子序列是透過從陣列中刪除一些元素獲得的，並將剩餘的元素按其原始順序保留。
因此，如果輸入類似於 [10, 2, -9, 5, 19] 且 k = 2，則輸出將為 36，因為子序列為 [10, 2, 5, 19]。
為了解決這個問題，我們將遵循以下步驟：
ret := -inf
定義一個數組 dp 並將給定陣列複製到其中
定義一個雙端佇列 dq
將 v[0] 插入 dq 的開頭
n := v 的大小
ret := v[0]
對於初始化 i := 1，當 i < n 時，更新（將 i 增加 1），執行：
如果 i > k 且 dq 的第一個元素與 dp[i - k - 1] 相同，則
從 dq 中刪除第一個元素
dp[i] := dp[i] 和（如果 dq 為空，則 dp[i] + 0，否則 dp 的第一個元素 + dq[i]）中的最大值
當（dq 不為空且 dq 的最後一個元素 < dp[i]）時，執行：
從 dq 中刪除最後一個元素
將 dp[i] 插入 dq 的末尾
ret := ret 和 dp[i] 中的最大值
返回 ret
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
class Solution {
public:
int constrainedSubsetSum(vector<int>& v, int k) {
int ret = -inf;
vector<int> dp(v.begin(), v.end());
deque<int> dq;
dq.push_front(v[0]);
int n = v.size();
ret = v[0];
for (int i = 1; i < n; i++) {
if (i > k && dq.front() == dp[i - k - 1])
dq.pop_front();
dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] +
dq.front());
while (!dq.empty() && dq.back() < dp[i])
dq.pop_back();
dq.push_back(dp[i]);
ret = max(ret, dp[i]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {10,2,-9,5,19};
cout << (ob.constrainedSubsetSum(v, 2));
}輸入
{10,2,-9,5,19}, 2輸出
36
更新於： 2020-06-09
114 次檢視
廣告