Given an array of integers, find two non-overlapping contiguous sub-arrays such that the absolute difference between the sum of two sub-arrays is maximum.
intfindMaxAbsDiff(vector<int> A){ int n = A.size(); vector<int> midp(n), madp(n); midp[n-1] = madp[n-1] = A[n-1]; for(int i = n - 2, mi = A[n-1], ma = A[n-1]; i >= 0; i--) { mi = min(A[i], mi + A[i]); ma = max(A[i], ma + A[i]); midp[i] = mi; madp[i] = ma; } int res = 0; for(int i = 0, mi = 0, ma = 0; i < n - 1; i++) { mi = min(A[i], mi + A[i]); ma = max(A[i], ma + A[i]); res = max({res, abs(mi - midp[i+1]), abs(mi - madp[i+1]), abs(ma - midp[i+1]), abs(ma - madp[i+1]) }); } return res; }