I was wondering if anyone knows how to solve the following question. I have tried on-and-off for about a week now, but I cannot figure it out:
Given an array A of N (1 <= N <= 100,000) positive integers, is it possible to remove exactly two elements in the array in order to form a partition of the array into three contiguous subarrays with equal sums?
For example, if A = [1, 3, 4, 2, 2, 2, 1, 1, 2], you can remove the "4" and the second-to-last "2" in order to get the following array: A = [1, 3, REMOVED, 2, 2, REMOVED, 1, 1, 2].
This works because 1 + 3 = 2 + 2 = 1 + 1 + 2 = 4.
But in some cases it might not be possible. For instance, if A = [1, 1, 1, 1, 1, 1], it's impossible,
Something important to keep note of is that don't need to determine which elements to remove but rather whether or not it is possible (so just yes/no is enough).
I have been struggling for a really long time with this problem. It is a variant of the "partition an array into 3 parts with equal sums" problem since you're forced to drop two elements in the array here.
I have tried thinking of DP solutions with no luck. Does anyone know how I can solve this? I think prefix sums might be useful here.