資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中從三個陣列中獲取最大和，但不能連續選擇來自同一陣列的元素
在這個問題中，我們得到三個大小為N的陣列arr1[]、arr2[]和arr3[]。我們的任務是編寫一個C++程式來查詢這三個陣列中的最大和，條件是不能連續選擇來自同一陣列的元素。
問題描述
我們將透過選擇N個元素來找到最大和。第i個元素可以選擇來自陣列的第i個元素的和，即第i個和來自arr1[i]/arr2[i]/arr3[i]。還要記住，我們不能選擇兩個連續的元素，而這兩個元素都來自同一個陣列。
讓我們舉個例子來理解這個問題：
輸入
arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4輸出
50
解釋
對於i = 1，我們將考慮來自arr3的8作為和。對於i = 2，我們將考慮來自arr2的12作為和。對於i = 3，我們將考慮來自arr3的10作為和。對於i = 4，我們將考慮來自arr1的20作為和。和 = 8 + 12 + 10 + 20 = 50
解決方案方法
為了解決這個問題，我們將使用動態規劃方法，還需要記住到索引為止的和，以避免額外的計算。我們將建立一個二維矩陣DP[][]。索引i,j處的元素將是到第i個索引為止的元素的和，並使用第j個數組。我們將遞迴地找到當前元素，然後呼叫來自其他兩個陣列的下一個元素的和。
示例
程式演示了我們解決方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int findMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
if (index == n)
return 0;
if (DP[index][arrNo] != -1)
return DP[index][arrNo];
int maxVal = -1;
if (arrNo == 0){
maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
}
else if (arrNo == 1){
maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
}
else if (arrNo == 2){
maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
}
return DP[index][arrNo] = maxVal;
}
int main(){
int arr1[] = { 5, 8, 9, 20 };
int arr2[] = { 7, 12, 1, 10 };
int arr3[] = { 8, 9, 10, 11 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int DP[n][N];
memset(DP, -1, sizeof DP);
int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
cout<<"The maximum sum from three arrays such that picking elements consecutively from same is not allowed is "<<findMaxVal(val1, findMaxVal(val2, val3));
return 0;
}輸出
The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50
更新於：2020年10月15日
271 次瀏覽
廣告