資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式中至少包含k個距離元素的最大和子序列
在這個問題中，我們得到一個大小為n的陣列arr[]和一個數字k。我們的任務是編寫一個程式來查詢至少包含k個距離元素的最大和子序列。
問題描述 − 我們需要找到子陣列的和，這些子陣列的元素取自索引之間距離至少為k的陣列，並且和最大化。
讓我們來看一個例子來理解這個問題：
輸入
arr[] = {2, 3, 7, 9, 2, 8, 3}輸出
15
解釋
All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15解決方案方法
解決這個問題的一個簡單方法是找到所有滿足給定條件的可能的子陣列。找到所有陣列的和，並返回所有和中的最大值。
解決這個問題的一個更有效的方案是使用動態規劃方法，建立一個數組來儲存直到當前元素的最大和。對於當前元素，我們可以將其考慮在和中，也可以將其排除在和之外，選擇哪個可以增加直到當前索引的和。
如果我們將其考慮在和中，sum[i] = sum[i + k + 1] + arr[i+1]；否則將其排除在和之外，sum[i] = sum[i+1]。最後返回最大和，即sum[0]。
示例
程式說明了我們解決方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k){
int maxSumDP[N];
maxSumDP[N − 1] = arr[N − 1];
for (int i = N − 2; i >= 0; i−−) {
if (i + k + 1 >= N)
maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
else
maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
}
return maxSumDP[0];
}
int main() {
int N = 10, k = 2;
int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
cout<<"The maximum sum subsequence with at−least k distant elements is "<<calcMaxSubSeqSum(arr, N, k);
return 0;
}輸出
The maximum sum subsequence with at-least k distant elements is 230
更新於：2020年12月9日
245 次瀏覽
廣告