spot7.org logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML Categories

Can someone explain me why the following algorithm for LIS is not O(n)?


Your current implementation of lis/1 function is O(n), I don't see any reasons to doubt. But there is some problem. You implementation doesn't actually calculate valid LIS. Try

lis(lists:reverse([1,2,3,4,1,2]))

for error example. Longest increasing sequense is [1,2,3,4], right? But your algorith returns 6 as result.

  • First error in your algorithm in that you increase result each time, when you encountered element that greater than previous. But you should increase result only if current element is greater that greatest element of your current LIS. So (according example above) you should remember 4 and not increase result after you detected then 2 is greater than 1.

  • But this not only thing you have to do. Consider sequence 1 2 3 6 4 5. For 5 first elements LIS has length of 4. But there is TWO possible options there - either 1 2 3 4 or 1 2 3 6. Which you should take as actual LIS?

  • And so on, and so on...

Another example comes directly from wiki page.

Sequence [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] has LIS [0, 2, 6, 9, 13, 15] (e.g., 6 elements), but your algorythm says 9.

And, (correct me, if I'm wrong), LIS implementation must return subsequence itself, but not only its length.


Categories : Algorithm

Related to : Can someone explain me why the following algorithm for LIS is not O(n)?
Explain, one or more arrays php?
This is what you have from print_r($your_array_from_mysql): Array ( [0] => 1 [id] => 1 [1] => Dæk For [title_task_DK] => Dæk For ) Array ( [0] => 2 [id] => 2 [1] => Dæk Bag [title_task_DK] => Dæk Bag ) Array ( [0] => 3 [id] => 3 [1] => Dæk Alm. [title_task_DK] => Dæk Alm. ) Array ( [0] => 4 [id]

Categories : PHP
I Need Someone to Explain the Query Conditions
<> stands for != (does not equal to). It's pretty old school - most newer languages do not use that. Also, ? (a question mark) represents a parameter in a query. More info here.

Categories : Java
Could Anybody explain this Swift Code Regarding Option
Question mark is used for optionals unwrapping. But in this case it does nothing.

Categories : Swift
JAVA Arrays - Need somebody to explain what this code does?
(1) You declare int temp to store the value of variables that are being swapped in the array, so when you overwrite one of the array elements, you still have the variable value. You don't need to use an entire array for this. (2) The code you don't understand swaps the array values at numbers[i] and numbers[numbers.length - 1 - i], using temp as a placeholder.

Categories : Java
Please explain Java ^ operator with examples
^ condition operator is the XOR in more mathematic terms, which stand from Exclusive or. (see this) So the XOR to return true, your left hand side condition must be different from the right hand side condition otherwise is false. e.g your condition if ((x <= 19 & x >= 13) ^ (y <= 19 & y >= 13)) will return true only in these two cases: 1) (x <= 19 & x >= 13) is true and (y &

Categories : Java
Recently Add
why this assembly piece of code do jmp forever
Find out if segment is fully inside of polygon
Algorithm for coloring a hexagon tile map with minimum distance (3) for reoccurring colors
Sort pairs to be more consecutive
To find three unique numbers whose number of occurrence is even
Dealing with duplication between unit and integration tests
reflection and symmetry in back tracking queens
Big O analysis for method with multiple parameters
Divide Huge Array of Numbers in Buckets
Algorithm to find adjacent cells in a matrix
Why this code gives WA for Petersen Graph(codechef)?
Complexity of this prime number search algorithm
How to detect if a file has changed?
Given string x,y and z. Determine if z is a shuffle
Basic decryption for simple encryption algorithm
An efficient way to assign user_ids to huge dataset under certain conditions
What's a more efficient implementation of this puzzle?
Generating prime numbers in poly-time
What if I do not use G transpose in calculating Strongly Connected Components?
Dividing an array into optimum no of equal sum sublists
Counting derangements
How to iterate through all cases when partitioning objects
Algorithm: How to find closest element, having coordinates and dimension
Developing player rankings with ELO
How to transform two set of discrete points ( vectors ) to help plotting them on a common scale
Heap Sort Space Complexity
complex root finding algorithm
Every possible combination algorithm
RSA Cryptosystem - Retrieve m
Heap-like data structure with fast random access?
© Copyright 2017 spot7.org Publishing Limited. All rights reserved.