資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中陣列中兩個元素無法以 < K 的距離出現時的子序列最大可能和
在本教程中，我們將討論一個程式，以查詢陣列中子序列的最大可能和，其中沒有兩個元素在距離 < K 時出現。
為此，我們會得到一個包含 N 個整數和一個值 K 的陣列。我們的任務是找到包括元素的最大子序列和，這些元素不比 K 接近。
示例
#include <bits/stdc++.h>
using namespace std;
//returning maximum sum
int maxSum(int* arr, int k, int n) {
if (n == 0)
return 0;
if (n == 1)
return arr[0];
if (n == 2)
return max(arr[0], arr[1]);
int dp[n];
dp[0] = arr[0];
for (int i = 1; i <= k; i++)
dp[i] = max(arr[i], dp[i - 1]);
for (int i = k + 1; i < n; i++)
dp[i] = max(arr[i], dp[i - (k + 1)] + arr[i]);
int max = *(std::max_element(dp, dp + n));
return max;
}
int main() {
int arr[] = { 6, 7, 1, 3, 8, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << maxSum(arr, k, n);
return 0;
}輸出
15
更新於： 09-Sep-2020
82 次瀏覽
廣告