algorithm - Number of increasing subsequences in sequence of [0-9] elements -


in case sequence of unknown range value elements, question number of increasing subsequences in given sequence give solution in o(n^2).

i've heard of solution in o(9*n) in case of sequence composed of elements in interval [0,9] only. if know algorithm please let me know that.

here algorithm:

1)let's call dp[i] = number of increasing subsequences have last element i(0 <= <= 9). filled zeros.

2)now can iterate on sequence , compute dp in following way:
let's assume current element d(0 <= d <= 9). dp can updated this:

for prev = 0...d - 1     dp[d] += dp[prev] //continue 1 of previous sequences. dp[d] += 1 //start new sequence consists of 1 element.

3)after iterating on elements of sequence,
answer sum of dp[i] 0 <= <= 9.

note algorithm has desired complexity under assumption arithmetic operations have o(1) time complexity(that might not case because number of increasing subsequences can large).


Comments

Post a Comment

Popular posts from this blog

Linux vanilla kernel on QEMU and networking with eth0 -

i have downloaded , compiled vanilla linux kernel (3.7.1) used busybox ramdisk booted using qemu. qemu command line qemu-system-i386 -kernel bzimage -initrd ramdisk.img -append "root=/dev/ram rw console=ttys0 rdinit=/bin/ash" -nographic -net nic -net user everything goes well. however, can't use networking on vanilla kernel busybox. 'ifup eth0' tells me / # ifup eth0 ip: siocgifflags: no such device i googled internet can' clue... advice nice thank in advance. most there no driver (in example should e1000) loaded or device has name. in /sys/class/net/ should find listing of available net-devices. if there none (besides lo) driver not loaded. in qemu monitor type "info pci" , show pci-address of ethernet card. should this: ... bus 0, device 3, function 0: ethernet controller: pci device 8086:100e ... this device corresponds /sys/devices/pci0000:00/0000:00:03.0/. files "vendor" , "device" must c...
Read more

rdbms - what exactly the undo information lives in oracle? -

some docs says, there "undo tablespaces" implies should create tablespace undo imformation. some docs says, there "undo segment" implies undo information lives in normal tablespaces , use of it's segment. so, undo information lives , organized? earlier releases of oracle database used rollback segments store undo. oracle9i introduced automatic undo management, simplifies undo space management eliminating complexities associated rollback segment management. oracle recommends (oracle 9i , on words) use undo tablespace (automatic undo management) manage undo rather rollback segments. when creating undo tablespace, these automatically created: n undo segments (based on sessions parameter value) named _syssmun$ owned public (usable ops configuration) not manually manageable
Read more

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more