Matrix Chain Multiplication

Write a program to implement matrix chain multiplication.

Example:

Input:  array = {1,2,4,3}
Output: 20

Approach

C++

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

int matrixMultiplication(vector<int> &array)
{
    int n = array.size();

    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 1; i < n; i++)
    {
        dp[i][i] = 0;
    }

    for (int len = 2; len < n; len++)
    {
        for (int i = 1; i < n - len + 1; i++)
        {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++)
            {

                int q = dp[i][k] +
                        dp[k + 1][j] +
                        array[i - 1] * array[k] * array[j];
                if (q < dp[i][j])
                    dp[i][j] = q;
            }
        }
    }
    return dp[1][n - 1];
}

int main()
{
    vector<int> array = {1, 2, 4, 3};

    cout << matrixMultiplication(array);

    return 0;
}

Block swap algorithm for array rotation

Write a program for array rotation using a block swap algorithm.

The block swap algorithm for array rotation is an efficient algorithm that is used for array rotation. It can do your work in O(n) time complexity.

Example:

Input:  arr[]={4,8,6,1,2}, k = 3
Output: 1 2 4 8 6 

Approach

C++

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

void swapSubArray(int arr[], int start, int end, int k)
{
    for (int i = 0; i < k; i++)
    {

        //swap two varibales
        swap(arr[start + i], arr[end + i]);
    }
}
void blockSwapAlgo(int arr[], int k, int n)
{
    //base case if 0 elments or
    //elements are same as size of array
    if (k == 0 || k == n)
        return;
    if (k == (n - k))
    {
        swapSubArray(arr, 0, (n - k), k);
        return;
    }
    else if (k < (n - k))
    {
        swapSubArray(arr, 0, (n - k), k);
        blockSwapAlgo(arr, k, (n - k));
    }
    else
    {
        swapSubArray(arr, 0, k, (n - k));
        blockSwapAlgo((arr + n - k), (2 * k - n), k);
    }
}

int main()

{
    int arr[] = {4, 8, 6, 1, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    blockSwapAlgo(arr, k, size);
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Finding a Negative Cycle in the Graph

Find any cycle of negative weight in the given, if such a cycle exists.

Example:

Input:  edges={{1,2,3},{2,3,-5},{3,1,-2},{3,4,5}}
Output: Negative cycle: 3 1 2 3 

Approach

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FindNegCycleInGraph {
    static int n, m;

    // vector array to hold all
    // the edges
    static List<Edge> edges;

    static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        n = 4;
        m = 4;
        edges = new ArrayList<Edge>();
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(2, 3, -5));
        edges.add(new Edge(3, 1, -2));
        edges.add(new Edge(3, 4, 5));

        negativeCycle();
    }

    static void negativeCycle() {
        // array to hold the distance of
        // all nodes
        int[] dist = new int[n + 1];

        // array to hold the parent of
        // all nodes
        int[] parent = new int[n + 1];
        int x = 0;

        // iterate for all nodes
        for (int i = 0; i < n; ++i) {
            x = -1;

            // iterate for all the edges
            for (Edge e : edges) {

                // update the distance and
                // parent
                if (dist[e.a] + e.cost < dist[e.b]) {
                    dist[e.b] = dist[e.a] + e.cost;
                    parent[e.b] = e.a;
                    x = e.b;
                }
            }
        }
        // if no cycle
        if (x == -1) {
            System.out.print("No negative cycle found. ");
        }

        // else cycle is present
        else {
            for (int i = 0; i < n; ++i)
                x = parent[x];

            List<Integer> cycle = new ArrayList<Integer>();
            for (int v = x;; v = parent[v]) {
                cycle.add(v);
                if (v == x && cycle.size() > 1)
                    break;
            }
            Collections.reverse(cycle);

            System.out.print("Negative cycle: ");
            for (int v : cycle)
                System.out.print(v + " ");
            System.out.println();
        }
    }

    // static class of the edges
    static class Edge {
        int a, b, cost;

        public Edge(int a, int b, int cost) {
            super();
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        public int getA() {
            return a;
        }

        public void setA(int a) {
            this.a = a;
        }

        public int getB() {
            return b;
        }

        public void setB(int b) {
            this.b = b;
        }

        public int getCost() {
            return cost;
        }

        public void setCost(int cost) {
            this.cost = cost;
        }

    }

}

C++

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

//structute of the edges
struct Edge
{
    int a, b, cost;
};

int n, m;

//vector array to hold all
//the edges
vector<Edge> edges;
const int INF = INT_MAX;

void negativeCycle()
{
    //array to hold the distance of
    //all nodes
    vector<int> dist(n + 1);

    //array to hold the parent of
    //all nodes
    vector<int> parent(n + 1, -1);
    int x;

    //iterate for all nodes
    for (int i = 0; i < n; ++i)
    {
        x = -1;

        //iterate for all the edges
        for (Edge e : edges)
        {

            //update the distance and
            //parent
            if (dist[e.a] + e.cost < dist[e.b])
            {
                dist[e.b] = dist[e.a] + e.cost;
                parent[e.b] = e.a;
                x = e.b;
            }
        }
    }
    //if no cycle
    if (x == -1)
    {
        cout << "No negative cycle found.";
    }

    //else cycle is present
    else
    {
        for (int i = 0; i < n; ++i)
            x = parent[x];

        vector<int> cycle;
        for (int v = x;; v = parent[v])
        {
            cycle.push_back(v);
            if (v == x && cycle.size() > 1)
                break;
        }
        reverse(cycle.begin(), cycle.end());

        cout << "Negative cycle: ";
        for (int v : cycle)
            cout << v << ' ';
        cout << endl;
    }
}

int main()
{
    n = 4, m = 4;
    edges.push_back({1, 2, 3});
    edges.push_back({2, 3, -5});
    edges.push_back({3, 1, -2});
    edges.push_back({3, 4, 5});
    negativeCycle();
    return 0;
}

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums ={10,9,2,5,3,7,101,18}
Output: 4

Approach

Java

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        System.out.println(lengthOfLIS(nums));
    }

    static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int dp[] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            if (ans < dp[i])
                ans = dp[i];
        return ans + 1;
    }

}

C++

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

int lengthOfLIS(vector<int>& nums) 
{
        int n=nums.size();
        vector<int> dp(n,1);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                      dp[i]=max(dp[i],1+dp[j]);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
             if(ans<dp[i])
                   ans=dp[i];
        return ans;
}

int main()
{
    vector<int> nums={10,9,2,5,3,7,101,18};
    cout<<lengthOfLIS(nums);
    return 0;
}

0–1 Knapsack problem

Find the maximum profit which we get after including the elements whose sum of weights is less than or equal to the capacity of the knapsack

Example:

Input:  profit={3,4,5,2,6,7}, weight={1,3,4,2,5,8}, capacity=13
Output: 18   //i.e 3+4+5+6

Approach 1: Using recursion

Java

public class Knapsack01problem {
    public static void main(String[] args) {
        int[] profit = { 3, 4, 5, 2, 6, 7 };
        int[] weight = { 1, 3, 4, 2, 5, 8 };
        int capacity = 13;

        System.out.println(knapSack(profit, weight, capacity, profit.length - 1));
    }

    // function to find the maximum profit
    // we can get after putting all elements whose
    // capacity of weight is less then or equal to capacity
    static int knapSack(int[] profit, int[] weight, int capacity, int n) {

        // base case if their is no elements
        // or capacity is zero then return 0
        if (n == -1 || capacity == 0)
            return 0;

        // if the weight of current element is
        // greater than the value of the remaining
        // capacity then ignore the current element
        if (weight[n] > capacity)
            return knapSack(profit, weight, capacity, n - 1);

        // else the answer will we max after including
        // the current element or by excluding the current element
        else
            return Math.max(knapSack(profit, weight, capacity, n - 1),
                    profit[n] + knapSack(profit, weight, capacity -
                         weight[n], n - 1));
    }
}

C++

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


//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
int knapSack(vector<int> profit,vector<int> weight,int capacity,int n)
{

    //base case if their is no elements
    //or capacity is zero then return 0
    if(n==-1||capacity==0)
       return 0;

    //if the weight of current element is 
    //greater than the value of the remaining 
    //capacity then ignore the current element
    if(weight[n]>capacity)
       return knapSack(profit,weight,capacity,n-1);

    //else the answer will we max after including
    //the current element or by excluding the current element
    else
      return max(knapSack(profit,weight,capacity,n-1),
          profit[n]+knapSack(profit,weight,capacity-weight[n],n-1));
}
int main()
{
    vector<int> profit={3,4,5,2,6,7};
    vector<int> weight={1,3,4,2,5,8};
    int capacity=13;

    cout<<knapSack(profit,weight,capacity,profit.size()-1);

    return 0;
    
}

Approach 2: Using memoization dynamic programming

Java

public class Knapsack01problem1 {
    public static void main(String[] args) {
        int[] profit = { 3, 4, 5, 2, 6, 7 };
        int[] weight = { 1, 3, 4, 2, 5, 8 };
        int capacity = 13;
        dp = new int[100][100];
        System.out.println(knapSackDP(profit, weight, capacity,
             profit.length - 1));
    }

    static int dp[][];

//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
    static int knapSackDP(int[] profit, int[] weight, int capacity, int n) {

        // base case if their is no elements
        // or capacity is zero then return 0
        if (n == -1 || capacity == 0)
            return 0;

        // if already calculated then return
        if (dp[n][capacity] != 0)
            return dp[n][capacity];
        // if the weight of current element is
        // greater than the value of the remaining
        // capacity then ignore the current element
        if (weight[n] > capacity)
            dp[n][capacity] = knapSackDP(profit, weight, capacity, n - 1);

        // else the answer will we max after including
        // the current element or by excluding the current element
        else
            dp[n][capacity] = Math.max(knapSackDP(profit, weight, capacity, n - 1),
            profit[n] + knapSackDP(profit, weight, capacity - weight[n], n - 1));
        return dp[n][capacity];
    }
}

C++

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

int dp[100][100];
//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
int knapSackDP(vector<int> profit,vector<int> weight,int capacity,int n)
{

    //base case if their is no elements
    //or capacity is zero then return 0
    if(n==-1||capacity==0)
       return 0;

   //if already calculated then return 
    if(dp[n][capacity]!=-1)
        return dp[n][capacity];
    //if the weight of current element is 
    //greater than the value of the remaining 
    //capacity then ignore the current element
    if(weight[n]>capacity)
       dp[n][capacity]=knapSackDP(profit,weight,capacity,n-1);

    //else the answer will we max after including
    //the current element or by excluding the current element
    else
      dp[n][capacity]=max(knapSackDP(profit,weight,capacity,n-1),
        profit[n]+knapSackDP(profit,weight,capacity-weight[n],n-1));
    return dp[n][capacity];
}
int main()
{
    vector<int> profit={3,4,5,2,6,7};
    vector<int> weight={1,3,4,2,5,8};
    int capacity=13;
    memset(dp,-1,sizeof(dp));
    cout<<knapSackDP(profit,weight,capacity,profit.size()-1);

    return 0;
    
}