DP hackerrank (stock maximize)

STock Maximize (iterative dP  and  branch & bound approach )



#include<bits/stdc++.h>
using namespace std;

long long int sell[1000000],a[1000000];

int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  long long int n,i,j,k,ans=0,m=0;
  cin>>n;

  for(i=0;i<n;i++)
   cin>>a[i];

  for(i=n-1;i>=0;i--)
   {
    if(m<a[i]) m=a[i];
    sell[i]=m;
   }

  for(i=0;i<n;i++)
  {
    if(sell[i]>a[i])
   ans+=sell[i]-a[i];
  }
  cout<<ans<<endl;
 }
return 0;
}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Branch And  Bound ----------------------------------------------------------




#include<bits/stdc++.h>

using namespace std;

int cost[60000],n;


int solve(int i,int tshare,int property)
{
  if(i==n)
  {
    if(tshare>=1)
     return (property+tshare*cost[i]);
     else
     return property;
  }

  int a,b,c;

  if(tshare>=1)
  {
  a=solve(i+1,tshare+1,property-cost[i]);     /// when buys

  b=solve(i+1,tshare,property);              /// when neither buys nor sells

  c=solve(i+1,tshare-1,property+cost[i]);   /// when sells

   return max(a,max(b,c));
  }

  if(tshare==0)
  {
     a=solve(i+1,tshare+1,property-cost[i]);  /// when buys

     b=solve(i+1,tshare,property);           /// when neither buys nor sells

     return max(a,b);
  }
}





int main()
{
 int t;
 cin>>t;
 while(t--)
 {

   cin>>n;

   for(int i=1;i<=n;i++)
   cin>>cost[i];
   cout<<solve(1,0,0)<<endl;;

 }
return 0;
}

DP (rectangles perimetere (spoj) ,,,Sherlock and cost (hackerrank) ) -->> 2^n DP

1) DP prblm of 2^n type ,(rectangles perimetre http://www.spoj.com/problems/MMAXPER/) #include using namespace std; int main() { int n; cin>> n; int a[n],b[n],dp[n][2],i,j,k; for(i=0;i>a[i]>>b[i]; dp[0][0]=a[0], dp[0][1]=b[0]; for(i=1;i using namespace std; int dp[100002][2]; int a[100002]; int main() { int t; cin>>t; while(t--) { int n,i,j,k; cin>>n; dp[0][0]=0; dp[0][1]=0; for(i=0;i>a[i]; for(i=1;i

Subarrays problems

1)   Number of subarrays of a array whose sum is K

2)  number of sub arrays of a array whose sum is multiple of  K

3) Number of subarrays of a array whose xor is Maximum (Lalit kundu post ,Quora )

http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

4) number of distinct subarrays of a array

http://stackoverflow.com/questions/17513359/number-of-distinct-subarrays

2) solution (number of subarrays whose sum is multiple of K)

#include<bits/stdc++.h>

using namespace std;

int B[1000];

int main()

{

  int n,k;

  cin>>n>>k;

  int A[n];

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

        cin>>A[i];

int s,i,ans;

B[0]++;

s = 0;

for (i = 0;i<= n-1;i++)

{

  s=(s + A[i])%k;

  B[s]++;

}

ans=0;

for(i = 0 ;i<= k-1;i++)

{

cout<<B[i]<<" ";

  ans+=(B[i]*(B[i]-1))/2;

}

cout<<endl;

  cout<<ans<<endl;

return 0;

}

edit distance
http://www.spoj.com/problems/EDIST/





#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;
int dp[2001][2001];
char a[400001],b[400001];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
long long int i,j,l1,l2;
//cout<<"enter first string "<<endl;
scanf("%s",a);

//cout<<"enter second string "<<endl;
scanf("%s",b);

//int dp[100][100];
l1=strlen(a);
l2=strlen(b);

 for(j=0;j<=l2;j++)
   {dp[0][j]=j; }

for(j=0;j<=l1;j++)
   {dp[j][0]=j;}

for(i=1;i<=l1;i++)
{
 for(j=1;j<=l2;j++)
 {
   if(a[i-1]==b[j-1])
   dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]));

   else
   dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1));;
 }

}

//cout<<dp[l1][l2];
cout<<dp[l1][l2]<<endl;
    }
return 0;
}

knapsack /unbounded knapsack

http://www.spoj.com/problems/KNAPSACK/    (simple knapsack)

http://www.spoj.com/problems/LKS/         (large knapsack)

Knapsack table filling

#include<stdio.h>

int maxi(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}



int main()
{
    int i,h,j,p,mm,summ=0,g,mw;
    scanf("%d",&mw);
    scanf("%d",&h);
int w[h+1],v[h+1];


for(i=1;i<h+1;i++)
{
scanf("%d",&w[i]);
scanf("%d",&v[i]);
}



v[0]=0;w[0]=0;


int n[h+1][mw+1];
v[0]=0;w[0]=0;


for(i=0;i<mw+1;i++)
    n[0][i]=0;
for(i=0;i<h+1;i++)
    n[i][0]=0;

for(i=1;i<h+1;i++)
{
    for(j=1;j<mw+1;j++)
    {
        p=j-w[i];
        if(p<0)                                      ///if small just copy the above row element
        {
        n[i][j]=n[i-1][j];
          continue;
        }
     n[i][j]=maxi((v[i]+n[i-1][p]),n[i-1][j]);
    }
}
summ=summ+n[h][mw];

printf("%d\n",summ);



return 0;
}




unbounded knapsack


#include<bits/stdc++.h>

using namespace std;

int findMaxValue(int weight[],int values[],int n,int capacity) {
   // temporary array where index 'j' denotes max value that can be fitted
   // in a knapsack of weight 'j'
   int knapsack[capacity+1];
   knapsack[0] = 0;
   //items[0] = -1;
   int i,j;
   for(j=1;j<=capacity;j++) {
      //items[j] = items[j-1];
      // as per our recursive formula,
      // iterate over all weights w(0)...w(n-1)
      // and find max value that can be fitted in knapsack of weight 'j'
      int max = knapsack[j-1];
      for(i=0;i<n;i++)
        {
         int x = j-weight[i];
         if(x >= 0 && (knapsack[x] + values[i]) > max)
          {
            max = knapsack[x] + values[i];
          }
         knapsack[j] = max;
        }
   }
   return knapsack[capacity];
}


int main()
{
        //freopen("txt.in","r",stdin);
    //freopen("atul.out","w",stdout);

int t;
cin>>t;
while(t--)
{
 long long int n,k,i,m=0,p,pp;
 cin>>n>>k;
int a[n];
 for(i=0;i<n;i++)
  {
   cin>>a[i];
  }

 cout<<findMaxValue(a,a,n,k)<<endl;
}
return 0;
}