# 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 conditionsGiven 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: 55Explanation: 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: 70Approach: 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 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