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: sqlite-users-boun...@sqlite.org [sqlite-users-boun...@sqlite.org] on behalf of Igor Tandetnik [itandet...@mvps.org] Sent: Monday, October 15, 2012 6:05 PM To: sqlite-users@sqlite.org 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 sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users