SubSet Sum Problem Using Dynamic Programming

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Solution:

#include<iostream>

#include<stdio.h>

using namespace std;

bool isSubsetSum(int set[], int n, int sum)

{

   

    bool subset[sum+1][n+1];

 

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

      subset[0][i] = true;

 

    // If sum is not 0 and set is empty, then answer is false

    for (int i = 1; i <= sum; i++)

      subset[i][0] = false;

 

     

     for (int i = 1; i <= sum; i++)

     {

       for (int j = 1; j <= n; j++)

       {

         subset[i][j] = subset[i][j-1];

         if (i >= set[j-1])

           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];

       }

     }

 

    

 

     return subset[sum][n];

}

 

int main()

{

    int T = 0 ;

    cin>>T;

    int *a;

    int n = 0;

    int sum = 0 ;

    for(int t = 0 ; t < T ; t++)

    {

            cin>>n;

            a = new int[n];

            for(int i = 0 ; i < n ; i++)

            {

                    cin>>a[i];

            }

            

            cin>>sum;

  if (isSubsetSum(a , n , sum ) == true)

     cout<<"YES"<<endl;

  else

     cout<<"NO"<<endl;

     delete []a;

  }

  return 0;

}

ZigZag Sequence Problem Top Coder 03 Semi Finals 3

Level Of the Problem ;-   EASY

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

SOLUTION:

#include<iostream>

#include<vector>

using namespace std;

int main()

{

    int T = 0 ; 

    int N = 0 ;

    cin>>T;

    vector<int>num;

    vector<int> sol;

    vector<int>sign; // USED TO STORE THE SIGN OF LAST TWO ELEMENTS

    for(int t = 0 ; t < T ; t++)

    {

            cin>>N;

            num.clear();

            num.resize(N);

            sol.clear();

            sol.resize(N+1);

            sign.clear();

            sign.resize(N);

            for(int i = 0 ; i < N ; i++)

            {

                    cin>>num[i];

                    sol[i] = 1 ;

                    sign[i] = 0 ;

                    

            }

            sol[N]= 1 ;

            for(int i = 1 ; i < N ; i++)

            {

                    for(int j = 0 ; j < i ; j++)

                    {

                            if( j == 0)

                            {

                                

                                sign[i] = num[i] - num[j]; 

                                sol[i] = sol[j] + 1 ;

                            }

                            else if(  ( (sign[j] > 0) && (num[i] - num[j] < 0))  || ( (sign[j] < 0) && (num[i] - num[j] > 0) ) && ( sol[j] + 1 > sol[i]) )

                            {

                            sol[i] =  sol[j] +  1 ;

                            sign[i] = num[i] - num[j]; 

                                

                            }

                    }

            }  

            cout<<sol[N-1]<<endl;

    }

    cin.get();

    return 0;

}