Vivek, you did pretty good there.
I tried solving it through dynamic programming but failed to find the
optimal substructure.
_dufus
On Aug 26, 9:57 pm, Vivek S wrote:
> let A[i+1] = a[0] + a[1] + ... + a[i];
> let B[i+1] = b[0] + b[1] + ... + b[i];
> A[0] = B[0] = 0;
> sum of nos from i to j
let A[i+1] = a[0] + a[1] + ... + a[i];
let B[i+1] = b[0] + b[1] + ... + b[i];
A[0] = B[0] = 0;
sum of nos from i to j of a[] = A[j+1] - A[i]; // O(1) time
Thus O(n^2) sol can be obtained for this problem by finding the sub-array
sum in the range [i, j] for every i, j;
But I have not used the fact
