Monday, 25 January 2016

Some problems on sum of subarray that look similar

1) Given an array of non-negative integers and input $x$, find the subarray which sums exactly to $x$. Find $O(n)$ solution

2) No constraints on numbers on array, find the max sum subarray in $O(n)$ time.

3) Given an array of integers and an input $x$, find the subarray with sum closest to $x$ in $O(n\log n)$ time