Maybe I'm missing something (wouldn't surprise me) but I can think of O(n)
traversal of the array for doing this. Not in SQL of course but you should be
able to write a user function for it.
Pseudo-code:
lastchar='';
For (char c in array)
if (lastchar = '' || c = lastchar+1)
curseq.push(c);
else
curseq.clear();
curseq..push(c);
end
lastchar = c;
if (curseq.size() > longest.size())
longest = curseq;
end
end
print longest.size();
Michael D. Black
Senior Scientist
Advanced Analytics Directorate
Advanced GEOINT Solutions Operating Unit
Northrop Grumman Information Systems
________________________________________
From: [email protected] [[email protected]] on
behalf of Igor Tandetnik [[email protected]]
Sent: Monday, October 15, 2012 6:05 PM
To: [email protected]
Subject: EXT :Re: [sqlite] 5. Re: Sqlite, Is it possible to calculate the
length of the longest increasing subsequence using an UDF
On 10/15/2012 4:29 PM, Frank Chang wrote:
> Igor Tandetnik,
>
>>>> So what is the purpose of this whole exercise
>
> Following the project gurus's example sequence of -- 1,2,3,4,3,5,6,7,8,10
> -- the numeric sorted ascending subsequence is found to be
> 1,2,3,4,5,6,7,8,10 using an automatic variable containing the most recent
> monotically increasing sequence member value and traversing the array
> sequentially in Big-O(linear time).
What will this algorithm do for a sequence 1, 10, 2, 3, 4, 5, 6, 7, 8, 9
? What about 1, 7, 2, 8, 3, 9, 4, 5, 6?
Generally, there is no known algorithm to find the longest subsequence
in O(n) time. You seem to be describing a greedy algorithm: it will
certainly find *some* increasing subsequence, but not necessarily the
longest one.
In any case, you still haven't explained two things that are of interest:
a) Why do you care about the longest increasing subsequence in the first
place? What do you plan to do with it, once found? This is not a purely
academical exercise, I presume.
b) Why does the solution have to be in the form of a SQLite user-defined
function?
--
Igor Tandetnik
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
