array / matrix subarray/submatrix sum

Maximal Subarray Sum : O(n) scan-and-update dynamic programming, https://en.wikipedia.org/wiki/Maximum_subarray_problem, https://leetcode.com/problems/maximum-subarray

Maximal Submatrix Sum: given 2-D matrix, find the submatrix whose sum is largest
we can solve 1-D case in O(n), then for each possible (i, j), generate column[] = sum{columns[i..j]}, which can be done in O(n) time given it's accumulating, and then solve 1-D case in O(n).
in total, all possible (i, j) means O(n^2), prefix-sum column means O(n), solve 1-D case O(n), in total O(n^3)

Shortest Subarray Sum Equals K : prefix-sum + sort + hash-table: O(nlogn) time, O(n) storage; https://leetcode.com/problems/minimum-size-subarray-sum/

if it's positive only, sliding window can also work.

Longest Subarray Sum Equals K : prefix-sum + sort + hash-table: O(n) time, O(n) storage, https://leetcode.com/problems/maximum-size-subarray-sum-equals-k

class Solution {

public:

    int maxSubArrayLen(vector<int>& nums, int k) {

        int sum = , res = ;

        unordered_map<int, int> m;

        for (int i = ; i < nums.size(); ++i) {

            sum += nums[i];

            if (sum == k) res = i + ;

            else if (m.count(sum - k)) res = max(res, i - m[sum - k]);

            if (!m.count(sum)) m[sum] = i;

        }

        return res;

    }

};

Largest Subarray Sum A Less than K : change hash-table to a map, and lower_bound / upper_bound : prefix-sum + sort + BST : O(nlogn) time, O(n) storage; https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k

int best_cumulative_sum(int ar[],int N,int K)

{

    set<int> cumset;

    cumset.insert();

    int best=,cum=;

    for(int i=;i<N;i++)

    {

        cum+=ar[i];

        set<int>::iterator sit=cumset.upper_bound(cum-K);

        if(sit!=cumset.end())best=max(best,cum-*sit);

        cumset.insert(cum);

    }

    return best;

}

Rectangle: sum all possible [i, j] columns, and reduce the case to 1-D, in total O(n^2) * 1-D case.

Max Sum of Rectangle No Larger Than K : sum all possible [i, j] columns together, reduce to 1-D case, in total n^2*nlogn. https://leetcode.com/problems/max-sum-of-sub-matrix-no-larger-than-k/

巴特西

array / matrix subarray/submatrix sum

最新文章

热门文章