Answer to Question #325754 in C++ for Ridhi

Question

You are given an array of N non-negative integers: A₁, A₂, ..., A_N. An alternating subsequence is a subsequence in which the indices of any two consecutive elements differ by exactly two in the original array. That is, if A_i1, A_i2, ..., A_ik is some subsequence, then for it to be an alternating subsequence, (i₂ - i₁ = 2), (i₃ - i₂ = 2), and so on should all hold true. Among all alternating subsequences, find the one which has maximum sum of elements, and output that sum.

Answer 1

#include <iostream>
using namespace std;


int max_alt_subseq(int A[], int n) {
    int sum1=0, sum2=0;


    for (int i=0; i<n; i++) {
        if (i%2) {
            sum1 += A[i];
        }
        else {
            sum2 += A[i];
        }
    }
    return sum1 > sum2 ? sum1 : sum2;
}

int main() {
    int A[] = { 1, 2, 3, 4, 5, 4, 3, 2, 1};
    int n = sizeof(A) / sizeof(A[0]);

    int sum = max_alt_subseq(A, n);

    cout << "The maximum sum of alternative subsequences is " << sum << endl;

    return 0;
}