Maximum Sum Subsequence made up of consecutive elements of different parity

  

#include <bits/stdc++.h>

using namespace std;

  

int dp[100][3];

  

int maxSum(int* arr, int i, int n,

           int prev, bool is_selected)

{

    

    if (i == n) {

        return 0;

    }

  

    

    

    int cur = abs(arr[i]) % 2;

  

    

    

    if (dp[i][prev] != -1) {

        return dp[i][prev];

    }

  

    

    

    

    if (i == n - 1 && is_selected == 0)

        return dp[i][prev] = arr[i];

  

    

    

    

    

    if (cur != prev) {

        dp[i][prev] = arr[i]

                      + maxSum(arr, i + 1,

                               n, cur, 1);

    }

  

    

    

    dp[i][prev]

        = max(dp[i][prev],

              maxSum(arr, i + 1, n,

                     prev, is_selected));

  

    

    return dp[i][prev];

}

  

void maxSumUtil(int arr[], int n)

{

  

    

    memset(dp, -1, sizeof(dp));

  

    

    

    

    cout << maxSum(arr, 0, n, 2, 0);

}

  

int main()

{

    int arr[] = { 1, 2, 6, 8, -5, 10 };

    int N = sizeof(arr) / sizeof(arr[0]);

    maxSumUtil(arr, N);

  

    return 0;

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets