Maximize sum that can be obtained from two given arrays based on given conditions

Maximize sum that can be obtained from two given arrays based on given conditions

Given two arrays A[] and B[] each of size N, the task is to find the maximum sum that can be obtained based on the following conditions:

• Both A[i] and B[i] cannot be included in the sum ( 0 ≤ i ≤ N – 1 ).
• If B[i] is added to the sum, then B[i – 1] and A[i – 1] cannot be included in the sum ( 0 ≤ i ≤ N – 1 ).

Examples:

Input: A[] = {10, 20, 5}, B[] = {5, 5, 45}
Output: 55
Explanation: The optimal way to maximize the sum is by including A[0] (= 10) and B[2] (= 45) in the sum. Therefore, sum = 10 + 45 = 55.

Input: A[] = {10, 1, 10, 10}, B[] = {5, 50, 1, 5}
Output: 70

Approach: This problem has Optimal substructure and Overlapping subproblems. Therefore, Dynamic Programming can be used to solve the problem. 
Follow the steps below to solve the problem:

• Initialize a arra, say dp[n][2], where dp[i][0] stores the maximum sum if element A[i] is taken into consideration and dp[i][1] stores the maximum sum if B[i] is taken into consideration.
• Iterate in the range [0, N – 1] using a variable, say i, and perform the following steps:
  • If i is equal to 0, then modify the value of dp[i][0] as A[i] and dp[i][1] as B[i].
  • Otherwise, perform the following operations:
    • Modify the value of dp[i][0] as max(dp[i – 1][0], dp[i – 1][1]) + A[i].
    • Modify the value of dp[i][1] as max(dp[i – 1], max(dp[i – 1][0], max(dp[i – 2][0], dp[i – 2][1]) + B[i])).
• After completing the above steps, print the max(dp[N-1][0], dp[N-1][1]) as the answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int MaximumSum(int a[], int b[], int n) {               int dp[n][2];                  dp[0][0] = a[0];     dp[0][1] = b[0];             for (int i = 1; i < n; i++) {                  dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i];                     dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);                     if (i - 2 >= 0) {             dp[i][1] = max(dp[i][1],                            max(dp[i - 2][0],                                dp[i - 2][1])                                + b[i]);         }         else {                                       dp[i][1] = max(dp[i][1], b[i]);         }     }             return max(dp[n - 1][0], dp[n - 1][1]); }    int main() {          int A[] = { 10, 1, 10, 10 };     int B[] = { 5, 50, 1, 5 };     int N = sizeof(A) / sizeof(A[0]);             cout << MaximumSum(A, B, N);     return 0; }

Output:

70

Time Complexity: O(N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer DSA Live Classes

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets