Here's an interview question I've seen on a few sites. People claim that an
O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.
Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.
(2, -1, -2, 1, -4, 2, 8)
((1, 4), (5, 6))
The output above is the indices of these two subarrays:
((-1, -2, 1, -4,), (2, 8))
I've been trying to reduce this problem to the Maximum subarray problem but with no success.