Skip to content

Commit

Permalink
Famous problems
Browse files Browse the repository at this point in the history
  • Loading branch information
ShivanshJ committed Mar 28, 2017
1 parent c1c9cb6 commit ef0f0eb
Show file tree
Hide file tree
Showing 3 changed files with 172 additions and 0 deletions.
46 changes: 46 additions & 0 deletions Sub-array (no adjacent elements)(Princess Farida).cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,46 @@
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

//Subset Sum Problem
//Can the set of numbers be divided into two sets with equal weights

//Explanation: http://www.ideserve.co.in/learn/set-partition-problem-recursion

#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)

int mon[]={5,2,1,10,7,3};
int best=0;

int mx(int a, int b)
{ return a>b?a:b ;
}

void gold(int n, int sum)
{
if(n<-2)
return;


//Base cases
//Note: n==-2, since last element will be added only when gold(0-2,sum+mon[0])
if(n==-2 || n==-1 )
{ if(best < sum)
best=sum;
return;
}

gold(n-2,sum+mon[n]); //Case1: Include, then go down by two, cuz no adjacent
gold(n-1,sum); //Case2: Exclude, then shift by 1;


return;
}

int main()
{ int n=sizeof(mon)/sizeof(mon[0]);
gold(n-1,0);
cout<<best;
return 0;
}
62 changes: 62 additions & 0 deletions Sub-array Non-contiguous.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,62 @@
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include<iostream>
using namespace std;

#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
#define RF(i,a,b) for(int i= (int)(a) ; i > (int)(b) ; i--)


//Non CONTIGUOUS
// to make it non-c... we take sum from S[i-2] + current position or we take it for series ending at S[i-1]

//........................extra note: for recursion, the function are would be:
// int func( int a[], sum, int i)
// ..
// func(a, sum + a[i], i-2)
// func(a, sum, i-1)


int mx(int a , int b)
{ a>b?cout<<a:cout<<b;
cout<<endl;

return a>b?a:b;

}


// reasoning at: http://code-em-up.blogspot.in/2012/07/question-given-unsorted-array-of.html

void sum(int a[10], int n)
{


int sol[10]; //New matrix memoized version

sol[0]=a[0];
sol[1]=a[1];

F(i,2,n)
sol[i] = mx( (sol[i-2] + a[i]) , sol[i-1] );

int res=sol[0];

F(j,1,n)
if(res<sol[j])
res=sol[j];

cout<<"Final greatest sum in non- contiguous subarray is: "<<res;

}


int main()
{ int a[10]= {-11,4,-2,8,-10,4,-3,4,3};

int n=sizeof(a)/sizeof(a[0]);

sum(a,n);

}
64 changes: 64 additions & 0 deletions Sub-array contiguous.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,64 @@
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include<iostream>
using namespace std;

#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
#define RF(i,a,b) for(int i= (int)(a) ; i > (int)(b) ; i--)


//Contiguous sum maximum;
// (x,x,x,x) <- S[i] considering is better then , (x,x,x)<-S[i-1] + a[i] .... Comparing this new one with old
// Thus, S[i]=max(S[i-1] + a[i] ,a[i])

//........................extra note: for recursion, the function are would be:
// int func( int a[], sum, int i)
// ..
// func(a, sum + a[i], i-1)
// func(a, a[i], i-1)


int mx(int a , int b)
{ a>b?cout<<a:cout<<b;
cout<<endl;

return a>b?a:b;

}

//NOTE : This memoized just makes sure it memorises the previousl computed value of sum for each
//Fine reasoning at: http://blog.saadtaame.org/2016/06/the-maximum-contiguous-subarray-problem.html

//IMP : https://people.cs.clemson.edu/~bcdean/dp_practice/

void sum(int a[10], int n)
{


int sol[10]; //New matrix memoized version

sol[0]=a[0];

F(i,1,n)
sol[i] = mx( (sol[i-1] + a[i]) , a[i] );

int res=sol[0];

F(j,1,n)
if(res<sol[j])
res=sol[j];

cout<<"Final greatest sum in contiguous subarray is: "<<res;

}


int main()
{ int a[10]= {-11,4,-2,8,-10,4,-3,4,3};

int n=sizeof(a)/sizeof(a[0]);

sum(a,n);

}

0 comments on commit ef0f0eb

Please sign in to comment.