Meet-in-the-middle is algorithm which allows us to solve O(2^n) complexity problems for O(2^n/2) time. In this problem you can use meet-in-the-middle: divide the peal into two peals b = {a1 a2 a3 . . . an/2}, c = {an/2 + 1, a2, . . . an}. Then calculate all subvalues of b and store it in s1, same for c and store in s2.Then sort s1 and s2. Now you must calculate Min(pealsum - 2 * (s1j + s2k)).This algo takes O((2^(n /2))^2) time instead of O(2^n), but   O((2^(n /2))^2) = O(2^n). Notice that s2 is sorted then we can use binray_search then we have O(2^(n/2)log(2^n/2))=O(2^(n/2) *(n/2)).

Edited by author 17.10.2011 20:50

Hello, i am learning about meet in the meedle, please explain why Min(pealsum - 2 * (s1j + s2k)) thanks (Sorry for my poor english)

I also haven't understood  Min(pealsum - 2 * (s1j + s2k)). I'd appreciate if someone explain it. But, you can calculate s1 and s2 as sum of all possible combinations: +/-a1 +/-a2... ++/-an and +/-b1 +/-b2... ++/-bn. Then find min(s1j + s2k). Here `meet in the middle' to reduce complexity, sort s2 and use binary search for lookup. Does it make sense?