|
|
back to boardCommon BoardGiven 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 ? |
|
|
