資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式：在陣列中找到最大子序列和，且子序列中任意兩個元素的距離不小於 K
在這個問題中，我們給定一個大小為 n 的陣列 arr[] 和一個整數 k。我們的任務是建立一個程式來找到一個子序列的最大可能和，使得陣列中沒有兩個元素的距離小於 K。
問題描述 - 我們需要找到子序列的最大和，該子序列考慮了彼此之間距離為 k 的元素。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2輸出
16
解釋
All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16解決方案方法
解決這個問題的方法是使用動態規劃。對於解決方案，我們將找到陣列當前元素之前的最大可能和。並將其儲存到 DP[i] 中，為此我們將找到最大可能的和。對於第 i 個索引，我們需要檢查添加當前索引值是否會增加子序列和。
if( DP[i − (k+1)] + arr[i] > DP[i − 1] ) −> DP[i] = DP[i − (k+1)] + arr[i] otherwise DP[i] = DP[i−1]
動態陣列的最大元素給出最大子序列和。
演算法
初始化 -
maxSumSubSeq = −1, maxSumDP[n]
步驟 1 -
Initialize maxSumDP[0] = arr[0]
步驟 2 -
Loop for i −> 1 to n.
步驟 2.1 -
if i < k −> maxSumDP[i] = maximum of arr[i] or maxSumDP[i− 1].
步驟 2.2 -
else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].
步驟 3 -
Find the maximum value of all elements from maxSumDP and store it to maxSumSubSeq.
步驟 4 -
Return maxSumSubSeq
示例
程式說明了我們解決方案的工作原理，
#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumSubSeq(int arr[], int k, int n) {
int maxSumDP[n];
int maxSum = −1;
maxSumDP[0] = arr[0];
for (int i = 1; i < n; i++){
if(i < k ){
maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
}
else
maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k +
1)] + arr[i]);
}
for(int i = 0; i < n; i++)
maxSum = retMaxVal(maxSumDP[i], maxSum);
return maxSum;
}
int main() {
int arr[] = {6, 2, 5, 1, 9, 11, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"The maximum sum possible for a sub−sequence such
that no two elements appear at a distance < "<<k<<" in the array is "<<calcMaxSumSubSeq(arr, k, n);
return 0;
}輸出
The maximum sum possible for a sub−sequence such that no two elements appear at a distance < 2 in the array is 16
更新於：2020-12-09
231 次檢視
廣告