(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not )
I've got an optimization problem where I need to choose from one of several options to maximize a quantity.
Each of those options is an array of numbers of arbitrary length, and each of the elements is strictly non-increasing (either decreasing or not changing), moving from left to right.
Here is an example, stacking them row-wise:
87643 99732 76534 87651 64311
I can only choose the leftmost in the stack, and after I choose it, it's gone. The naive way to do this would be to look for the maximum from the first column, take it, then redefine the problem with the removed element out and then continue.
87643 9732 76534 87651 64311 val = 9 out = (2) 87643 732 76534 87651 64311 val = 18 out = (2) 7643 732 76534 87651 64311 val = 26 out = (2, 1)
and so on
This is sort of slow given the size of my array, and how it's likely to scale. Are there any better alternatives?
No idea why the downvotes but anyway I figured out that I can just concatenate a vector of indices (1 through N) to each array, concatenate the 2d arrays, then sort by the value. I select elements until the cumulative sum matches what I want.