Answer to Question #307502 in C for lazy_coder

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 <stdio.h>

int main()
{
    int maxsum, sum;
    int i, n;
    int array[] = {1, 3, 5, 6, 9, 11, 5, 2, 1, 21, 23, 25, 3, 5, 7, 9, 11, 13, 26, 28};
    n = sizeof(array)/sizeof(array[0]);
    // if enter the array manually
    //
    // printf("Enter N: ");
    // scanf("%d", &n);
    // int array[n];
    // printf("Enter array: \n");
    // for (i = 0; i < n; i++)
    //       scanf("%d", &array[i]);
    int alt_seq [n];
    int temp_arr [n];
    int jn = -1;
    int j, maxj;
   
    printf("\nArray:\n");
    for(i=1; i < n; i++)
        printf("%d ", array[i]);
    maxsum = 0;
    sum = 0;
    for(i=1; i < n; i++)
    {
        if (array[i] - array[i-1] == 2)
        {
              if (sum == 0)
            {
                  sum += array[i-1];
                  jn++;
                temp_arr[jn] = array[i-1];                  
             }
            sum += array[i];
            jn++;
            temp_arr[jn] = array[i];                            
              if ((i == n-1) & (maxsum < sum))              
            {
                maxsum = sum;
                for (j=0; j <= jn; j++)
                    alt_seq[j] = temp_arr[j];
                maxj = jn;
                jn = -1;
            }
        }        
        else if (sum > 0)
        {            
            if (maxsum < sum)
            {
                maxsum = sum;
                for (j=0; j <= jn; j++)
                    alt_seq[j] = temp_arr[j];
                maxj = jn;
                jn = -1;
            }
            sum = 0;            
        }             
    }
    if (maxsum > 0)
    {
    printf("\n\nMax alternating subsequences: ");
    for (i = 0; i <= maxj; i++)
        printf("%d ", alt_seq[i]);
    printf("\n");
    printf("Maximum sum: %d \n", maxsum);
    }
    else
        printf("\n\nNo alternating subsequences\n");
   
    return 0;
}