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;}
Answer: Option A
Was this answer helpful ?
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 ?
Submit Solution