- Arrays, Dynamic Programming, Mathematical

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