Dp1

/* Example of Dynamic programmig
 using Tabular Method */

#include <stdio.h>
#define MAX(a,b) ((a>b)?a:b)
#define UPPERSEQ 1
#define LOWERSEQ 2

int get_subseq(int a,int b,int i) {
        if(i%2==0) {
                if(a==MAX(a,b))
                        return UPPERSEQ;
                else
                        return LOWERSEQ;
        }
        else {
                if(a==MAX(a,b))
                        return LOWERSEQ;

                else
                        return UPPERSEQ;
        }
}

int main(void) {
        const int n = 6;
        int i=2;
        int a[n] = { 1,3,2,6,4,2};
        int sum[n]; // our table that will keep track of old sums
        sum[0]=a[0];
        sum[1]=a[1];
        while(i<n){
                sum[i]=MAX((sum[i-2] + a[i]),sum[i-1]);i++;
        }
        printf("max : %d\n",sum[i-1]);
        // its not part of my example but just for fun we ill find the numbers
        //when sums will be equal
        if(sum[i-1] == sum[i-2]){
                printf("Elements can not be decided because there are two same max sums exist");
                return 1;
        }
        printf("elements : ");
        for(int j=0;j<n;j++) {                                                                   if(get_subseq((sum[i-3]+a[i-1]),sum[i-2],i-1) == UPPERSEQ) {
                        printf("%d\t",a[j]);j++;
                }
                else
                        printf("%d\t",a[++j]);
        }
        return 0;
}