Tổng tối đa từ ba mảng sao cho việc chọn các phần tử liên tiếp từ cùng một không được phép trong C ++

Trong bài toán này, chúng ta được cung cấp ba mảng arr1 [], arr2 [] và arr3 [] đều có kích thước N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng lớn nhất từ ​​ba mảng sao cho chọn các phần tử liên tiếp từ cùng một mảng không được phép trong C ++.

Mô tả vấn đề

Chúng ta sẽ tìm tổng lớn nhất bằng cách chọn N phần tử. Phần tử thứ i =có thể được chọn trong tổng từ phần tử thứ i của mảng, tức là tổng thứ i là từ arr1 [i] / arr2 [i] / arr3 [i]. Ngoài ra, hãy nhớ rằng chúng ta không thể chọn hai phần tử liên tiếp có thể được chọn từ cùng một mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Bỏ qua

arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4

Đầu ra

50

Giải thích

Với i =1, chúng ta sẽ xem xét 8 cho tổng từ arr3. Với i =2, chúng ta sẽ xem xét 12 cho tổng từ arr2. Với i =3, chúng ta sẽ xem xét 10 cho tổng từ arr3. Với i =4, chúng ta sẽ xem xét 20 cho tổng từ arr1. Tổng =8 + 12 + 10 + 20 =50

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta sẽ sử dụng phương pháp lập trình động, chúng ta cũng cần ghi nhớ các tổng cho đến chỉ mục để tránh tính toán thêm. Chúng ta sẽ tạo một ma trận 2-D, DP [] []. Phần tử ở chỉ mục i, j sẽ là tổng các phần tử cho đến chỉ mục thứ i và sử dụng mảng thứ j. Chúng tôi sẽ tìm một cách đệ quy các phần tử cho hiện tại và sau đó gọi tổng các phần tử tiếp theo từ hai mảng còn lại.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50