Answer to Question #300527 in C for Sai

Question

You are given an array of N non-negative integers: A1, A2, ..., AN. 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 Ai1, Ai2, ..., Aik is some subsequence, then for it to be an alternating subsequence, (i2 - i1 = 2), (i3 - i2 = 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 <stdio.h>

int main()
{
    int maxsum, sum;
    int array[] = {1, 3, 5, 6, 9, 11, 5, 2, 1, 3, 5, 7, 9, 11, 13, 26, 28};
    int n = sizeof(array)/sizeof(array[0]);
    maxsum = 0;
    sum = 0;
    for(int i=1; i < n; i++)
    {
        if (array[i] - array[i-1] == 2)
        {
              if (sum == 0)
                  sum += array[i-1];
            sum += array[i];              
              if ((i == n-1) & (maxsum < sum))              
                 maxsum = sum;        
        }        
        else if (sum > 0)
        {            
            if (maxsum < sum)
                maxsum = sum;
            sum = 0;            
        }             
    }
    if (maxsum > 0)
        printf("Maximum sum: %d \n", maxsum);
    else
        printf("No alternating subsequences\n");
   
    return 0;
}