Sail E0 Webinar
Question
Complete the following dynamic programming implementation of the longest increasing subsequence problem:#includeint longest_inc_sub(int *arr, int len){      int i, j, tmp_max;      int LIS[len];  // array to store the lengths of the longest increasing subsequence       LIS[0]=1;      for(i = 1; i < len; i++)      {            tmp_max = 0;    for(j = 0; j < i; j++)    {         if(arr[j] < arr[i])         {     if(LIS[j] > tmp_max)      ___________;           }           }    LIS[i] = tmp_max + 1;      }      int max = LIS[0];      for(i = 0; i < len; i++) if(LIS[i] > max)    max = LIS[i];      return max;}int main(){      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;      int ans = longest_inc_sub(arr, len);      printf("%d",ans);      return 0;}
Options:
A .  tmp_max = LIS[j].
B .  LIS[i] = LIS[j].
C .  LIS[j] = tmp_max
D .  tmp_max = LIS[i].
Answer: Option A


tmp_max is used to store the maximum length of an increasing subsequence for any 'j' such that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.



Was this answer helpful ?
Next Question

Submit Solution

Your email address will not be published. Required fields are marked *

More Questions on This Topic :


Latest Videos

Latest Test Papers