Question: Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum?

Solution: A simple interview problem on O(n) space and O(n) time.
step 1: Take sum of all elements. o(n)
step 2: now traverse and keep sum till now as t and remaining sum as S-t . Look for least difference between them while traversing.