CSES : Increasing Subsequence - dynamic Programming

 Problem Statement:

You are given an array containing n$n$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer n$n$: the size of the array.

After this there are n$n$ integers x1,x2,…,xn$x_1,x_2,\dots ,x_n$: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• 1≤xi≤109$1\le x_i\le {10}^9$
  

Example

Input:
8
7 3 5 3 6 2 9 8

Output:
4




Full Video Explanation:

Youtube Video Explanation




Code:(C++)

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

int main() {

  int n;
  cin >> n;
  vector<int> dp;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    auto it = lower_bound(dp.begin(), dp.end(), x);
    if (it == dp.end()) {
      dp.push_back(x);
    } else {
      *it = x;
    }
  }
  cout << dp.size() << endl;
}

Hackerrank : Interview Prepration Kit ->Hash Tables: Ice Cream Parlor Approach

 Problem Statement:

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool their money to buy ice cream. On any given day, the parlor offers a line of flavors. Each flavor has a cost associated with it.

Given the value of  and the  of each flavor for  trips to the Ice Cream Parlor, help Sunny and Johnny choose two distinct flavors such that they spend their entire pool of money during each visit. ID numbers are the 1- based index number associated with a . For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.

Example

They would purchase flavor ID's  and  for a cost of . Use  based indexing for your response.

Note:

• Two ice creams having unique IDs  and  may have the same cost (i.e., ).
• There will always be a unique solution.

Function Description

Complete the function whatFlavors in the editor below.

whatFlavors has the following parameter(s):

• int cost[n] the prices for each flavor
• int money: the amount of money they have to spend

Prints

• int int: the indices of the two flavors they will purchase as two space-separated integers on a line

Input Format

The first line contains an integer, , the number of trips to the ice cream parlor.

Each of the next  sets of  lines is as follows:

• The first line contains .
• The second line contains an integer, , the size of the array .
• The third line contains  space-separated integers denoting the .

Constraints

Approach :

Since it is explicitly mentioned that the problem will use Hashmaps , our work has been cut out for us. The real crux part of the problem is that we need to find the pairs a[i] , a[j] both belonging to the array such that their sum is equal to the given number money.

    Now for this we can think of this like we will choose an number-a[i] from the array and then find the corresponding a[j] such that a[i] + a[j] = money or a[j] = money-a[i] . This kind of finding the element corresponding to and integer or string or float is very well achieved by the hashmaps. I will attach the links for the further reading of the hashmaps . 

    Now to the solution of the problem , we can initialize a hashmap h. We will store the values that have occured in the array as the key and their currosponding index in the original array will be the value in the hashmap. For example if the first value of the array is 10 ,  then in the hashmap h , h[10]=1. where 10 is key and 1 is the value.

    Like this for each element i in the array , we will check if the value we required value(i.e money-a[i]) is present in the hashmap , if present we will simply return the current value and found hashmap value and terminate the function , else we will append the value to the hashmap for future refrences.

Further Reading :

Hashmaps in Cpp

Hashmaps in java

Code :

(The Template code is already given , you just have to fill the function)

void whatFlavors(vector<int> cost, int money) {

    //make the hashmap
    unordered_map<int,int>u_map;

    //get the size of the array
    int n = cost.size();

    //Iterate over each element of array
    for (int i=0 ; i<n ; i++){
        //Find if the required element (Total - current_element) is already present in the hashmap
        auto k = u_map.find(money-cost[i]);
             
            //If present then print the elements and return 
            if ( k != u_map.end() ){
                cout<<k->second<<" "<<i+1<<endl;
                return ;
            }
        
        //If not present then add the possible element to the hashmap
        u_map[cost[i]] = i+1;
    }
}