arrays - How can we assure that a Bitonic sequence will be formed from one longest increasing subsequence and one longest decreasing subsequence? -

-

for example have array[]={1,3,2,7,4,6,8,9}.

longest increasing subsequence of array[]={1,3,4,6,8,9} , length=6.

longest decreasing subsequence of array[]={3,2} , length=2.

then bitonic subsequence of array[]={1,3,4,6,8,9}? if yes length=6.but length of bitonic subsequence =length of lis + length of lds -1, here not equal.

if no how can prove length of bitonic subsequence=length of lis+length of lds-1

correct me if wrong. thank you.

the formula correct , gives out 6 only... consider lis[](as lis array) , lds[] (as lds array).. when iterate left right reach position lis[index]=6 i.e. lis till array[7] 6.. lds[index=7] 1 (trivially 1 element maximum length of series)... lis[7]+lds[7]-1=(6+1-1)

now proof wanted bitonic sequence... lis[i],lds[i] represents longest increasing / decreasing sequence till i! now, want maximise that's why search on sample space! answer maximum of (lis[i]+lds[i]-1) 0<=i<=n-1 ... that -1 due repeated inclusion of element @ th position!


Comments

Post a Comment

Popular posts from this blog

Java 3D LWJGL collision -

-
i making 3d java game lwjgl library, , wondering how add collision detection, player not go through models. i using obj models. here objloader class, loads models: package renderengine; import java.io.bufferedreader; import java.io.file; import java.io.filenotfoundexception; import java.io.filereader; import java.util.arraylist; import java.util.list; import models.rawmodel; import org.lwjgl.util.vector.vector2f; import org.lwjgl.util.vector.vector3f; public class objloader { public static rawmodel loadobjmodel(string filename, loader loader){ filereader fr = null; try { fr = new filereader(new file("res/"+filename+".obj")); } catch (filenotfoundexception e) { system.err.println("couldn't load file!"); e.printstacktrace(); } bufferedreader reader = new bufferedreader(fr); string line; list<vector3f> vertices = new arraylist<vector3f...
Read more

spring - SubProtocolWebSocketHandler - No handlers -

-
i have ugly error during deploying spring app on jboss. 18:11:16,025 error [org.apache.catalina.core.containerbase.[jboss.web].[default-host].[/consumer]] (msc service thread 1-7) exception sending context initialized event listener instance of class org.springframework.web.context.contextloaderlistener: org.springframework.context.applicationcontextexception: failed start bean 'subprotocolwebsockethandler'; nested exception java.lang.illegalargumentexception: no handlers @ org.springframework.context.support.defaultlifecycleprocessor.dostart(defaultlifecycleprocessor.java:176) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor.access$200(defaultlifecycleprocessor.java:51) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor$lifecyclegroup.start(defaultlifecycleprocessor.java:346) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.s...
Read more

methods - python can't use function in submodule -

-
my folder structure this: pythonstuff/ program.py modulea/ __init__.py foo.py bar.py here's code bar.py : def hello(): print("hello, world!") here's code program.py : #!/usr/bin/env python3 modulea import bar bar.hello() i run $ python3 program.py somehow error: file "program.py", line 3, in <module> bar.hello() attributeerror: 'module' object has no attribute 'hello' edit: __init__.py file empty. edit2: after trying realized had bar.py in root directory contained hello() method. bar.py in modulea/ directory empty. add it import os __all__ = [] module in os.listdir(os.path.dirname(__file__)): if module != '__init__.py' , module[-3:] == '.py': __all__.append(module[:-3]) the init .py files required make python treat directories containing packages; done prevent directories common name, such string, unintentionally hiding v...
Read more