Timeline for Maximizing number of factors contributing in the sum of sorted array bounded by a value
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 16, 2012 at 5:06 | answer | added | fedja | timeline score: 0 | |
| Nov 15, 2012 at 13:20 | comment | added | fedja | It is linear, actually. Just realize that if $a_k$ to $a_m$ is the answer, then $i$ is just the middle term. Now just move three markers left to right, spending constant time on the updates of a few relevant quantities. I'll post the algorithm when I have more time unless somebody else does it earlier :-). | |
| Nov 14, 2012 at 13:28 | vote | accept | paramar | ||
| Nov 14, 2012 at 0:17 | comment | added | Tony Huynh | For your sum you are summing over the entire array, but in your example you want the best contiguous subarray. I assume your example is what you want. | |
| Nov 13, 2012 at 20:42 | comment | added | paramar | Why it does not? Can you explain? | |
| Nov 13, 2012 at 17:31 | answer | added | Tony Huynh | timeline score: 0 | |
| Nov 13, 2012 at 16:55 | comment | added | Tony Huynh | It seems that what you really want to find is $i,j,k$ such that $i<A[n]$ and $\sum_{l=j}^k |A[l]-i| \leq B$ and $k-j$ is as large as possible. As it stands your description does not match your example. | |
| Nov 13, 2012 at 13:51 | history | asked | paramar | CC BY-SA 3.0 |