Day-25.txt

                        Dynamic Programming Part-I


1.   Max Product Subarray

ANS.   1st approach ():

        int maxProduct(vector<int>& nums) {
        int n=nums.size();
        int res=nums[0],maxi=nums[0],mini=nums[0];
        for (int i=1;i<n;i++)
        {
            if (nums[i]<0)
            {
                swap(maxi,mini);
            }
            maxi=max(nums[i],nums[i]*maxi);
            mini=min(nums[i],nums[i]*mini);
            res=max(res,maxi);
        }
        return res;
    }


     2nd approach ():


2.   Longest Increasing Subsequence

ANS.   1st approach ():

3.   Longest Common Subsequence

ANS.   1st approach ():

        int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        vector<vector<int>> t(n+1,vector<int> (m+1,-1));
        for (int i=0;i<n+1;i++)
            t[i][0]=0;
        for (int i=0;i<m+1;i++)
            t[0][i]=0;
        
        for (int i=1;i<n+1;i++)
        {
            for (int j=1;j<m+1;j++)
            {
                if (text1[i-1]==text2[j-1])
                    t[i][j]=1+t[i-1][j-1];
                else
                    t[i][j]=max(t[i-1][j],t[i][j-1]);
            }
        }
        return t[n][m];
        s="";
        int i=n,j=m;
        while (i>0 && j>0)
        {
            if (text1[i-1]==text2[j-1])
            {
                s.push_back(text1[i-1]);
                i--;
                j--;
            }
            else if (t[i][j-1]>t[i-1][j])
                j--;
            else
                i--;
        }
        reverse(s.begin(), s.end());
        return s;
    }


4.   0-1 Knapsack

ANS.   1st approach ():

       int knapSack(int W, int wt[], int val[], int n) 
    { 
         int t[n+1][W+1];
         for (int i=0;i<n+1;i++)
             t[i][0]=0;
         for (int i=0;i<W+1;i++)
             t[0][i]=0;
         
         for (int i=1;i<n+1;i++)
         {
             for (int j=1;j<W+1;j++)
             {
                 if (wt[i-1]<=j)
                  t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j]);
                 else
                  t[i][j]=t[i-1][j];
             }
         }
         return t[n][W];
         
    }

5.   Ones and Zeroes

ANS.   1st approach ():

6.    Edit Distance

ANS.   1st approach ():

7.   Maximum Sum increasing Subsequence

ANS.   1st approach ():

8.    Matrix Chain Multiplication

ANS.   1st approach ():

        int MCM(int arr[],int lb,int ub, vector<vector<int>> &t)
    {
        if (lb==ub) return 0;
        if (t[lb][ub]!=-1)
          return t[lb][ub];
        int mini=INT_MAX;
        for (int k=lb;k<=ub-1;k++)
        {
            int tempans=MCM(arr,lb,k,t)+MCM(arr,k+1,ub,t)+arr[lb-1]*arr[k]*arr[ub];
            mini=min(mini,tempans);
        }
        return t[lb][ub]=mini;
    }
    int matrixMultiplication(int N, int arr[])
    {
        vector<vector<int>> t(N,vector<int> (N,-1));
        return MCM(arr,1,N-1,t);
    }