- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In this problem, we are given three arrays arr1[], arr2[], and arr3[] all of size N. Our task is to create a program to find the Maximum sum from three arrays such that picking elements consecutively from same is not allowed in C++.

We will find the maximum sum by choosing N elements. i=th element can be chosen of the sum from the i-th element of the array i.e. ith sum is from arr1[i]/ arr2[i]/ arr3[i]. Also, keep in mind that we cannot choose two consecutive elements that can be chosen from the same array.

**Let’s take an example to understand the problem,**

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

50

For i = 1, we will consider 8 for sum from arr3. For i = 2, we will consider 12 for sum from arr2. For i = 3, we will consider 10 for sum from arr3. For i = 4, we will consider 20 for sum from arr1. Sum = 8 + 12 + 10 + 20 = 50

To solve the problem, we will be using the dynamic programming approach, we also need memorization of sums till the index to avoid extra calculations. We will create a 2-D matrix, DP[][]. The element at index i,j will be the sum of elements till i-th index and using j-th array. We will recursively find elements for the current and then call the sum of the next elements from the other two arrays.

Program to illustrate the working of our solution,

#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

- Related Questions & Answers
- Maximum sum by picking elements from two arrays in order in C++ Program
- Find three element from different three arrays such that that a + b + c = sum in Python
- Maximum sum from a tree with adjacent levels not allowed in C++
- Maximum subsequence sum such that no three are consecutive
- Python - Make pair from two list such that elements are not same in pairs
- Maximum subsequence sum such that no three are consecutive in C++ Program
- Maximum sum of increasing order elements from n arrays in C++
- Find three closest elements from given three sorted arrays in C++
- Pick maximum sum M elements such that contiguous repetitions do not exceed K in C++
- Maximum sum such that no two elements are adjacent in C++
- Maximum sum of increasing order elements from n arrays in C++ program
- Find minimum sum such that one of every three consecutive elements is taken in C++
- Maximum sum subarray such that start and end values are same in C++
- Find sub-arrays from given two arrays such that they have equal sum in Python
- Maximum sum subarray such that start and end values are same in C++ Program

Advertisements