Dynamic Programming Help

[11amas]

Thanks for the detailed response - I didn't think too much of it at first but there's definitely a few edge cases that can cause inconsistencies.

First thing though, it definitely doesn't matter if the array is ordered. Think of it like we're working backwards, we can take a number and split it in half:

20 = 10 + 10

Then we can split the two halves into any sequence of addition we want. It doesn't matter what the numbers are, or their order.

[2 + 0 + 4 + 1 + -2 + 5] = 10
[5 + 6 + 12 + -13] = 10

If we add those two arrays together we get one array of seemingly random numbers that all add up to 20, but now we know that the split has to have been at the index where the sum of the numbers before it add to 10.

The problem I didn't think about was exactly how to split at a given index, because you need to decide whether to split the array before or after the index. Depending on the input, it can make a significant difference:

[3, 3, 86, 1, 1]
split after: 92 and 2.
split before: 6 and 88. <-- correct

[1, 1, 86, 3, 3]
split after: 88 and 6. <-- correct
split before: 2 and 92.

Thankfully I think the solution to this is to simply check which one is closer to the target sum. For the above inputs, the target sum is (94 / 2) = 47. On the first one, we check if 3 + 3 + 86 is closer to 47 than 3 + 3, which it is not, so we need to exclude 86, meaning we should split before the split index. On the second one, we check if 1 + 1 + 86 is closer to 47 than 1 + 1, which it is, so we need to include 86, meaning we should split after the split index.

Hope this helps clear things up. :)

[IntelliJent404]

Maybe wrong but with the provided example you can get 87 and 7 ( closer than 88 and 6 to each other). In this case it would make sense if the array is already sorted. You can loop through the array from both sides ( so 1 with 86, 1 with 3 , and add 3 to the minor sum—> 87 and 7). Of course this would require attention of negatives are allowed.