Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
* The sub-arrays should not overlap.

example- array [2, -1, -2, 1, -4, 2, 8]
answer - first (-1 -2 1 -4) Second (2 8), Maximum difference = (10-(-6)) 16.

Can you please provide recurrence relation for Dynamic Programming to solve this?It would be nice if it is accompanied with explanation.

Edited by author 12.06.2013 00:01

Edited by author 12.06.2013 00:01

But you can do it in N^4 time also by using brute force , You appear this question during interview process ?