How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, First, find a prefix-sum on each column (O(N^2)). This

How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers...

First, find a prefix-sum on each column (O(N^2)). This is done so that we can later on compute the sum of consecutive rows in O(1) complexity.
Now, observe all possible row-pairs (O(N^2)), and for each pair, you can see that we can get the sum of each "column" in O(1) complexity. This will provide us with a feeling that you can view the contiguous rows within each row-pair as only one row per column. Thus, we have a somewhat a one-dimensional array of column sums.
To find the maximum contiguous elements in one-dimensional array, there is a Kadane's algorithm which is O(N).
All the steps above gives O(N^3) algorithm.

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0. e.g. array[n]={1, 3, -4, 8, -1}

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0.
e.g. array[n]={1, 3, -4, 8, -1} k=10
because 3+8-1=10, then return 1;
What is the best time complexity??

Create the prefix sum array b[j]=b[j-1]+a[j] where j is from 0 O(n)
For each value in array b just try to find another value val where val-b[i]=k use hash table O(n)
For this condition, subarray (contiguous) like minimum subarray or specific subarray, we can take advantage prefix sum array
If you get the idx for Prefix sum array is from i to j
The subarray is from i+1 to j

Find the subvector with the sum closest to 0 , whats the best algorithm [O(nlgn)] you can design for this ?

Find the subvector with the sum closest to 0 , whats the best algorithm [O(nlgn)] you can design for this ?

Use prefix sum array, you should consider the first element
So after you get the minimum pair, you should compare it with a[0]…

Suppose we wish to find the subvector with the sum closest to zero

Suppose we wish to find the subvector with the sum closest to zero

1. First calculate curr[i]=curr[i-1]+a[i];
2. Find the curr[u]-curr[l] which is 0 or close to 0
3. So from a[l+1] to a[u] is the subvector we want
Can be done nlogn, if you sort the array curr on the 2 step