Sub-array lintcode Problem Set Summary C++


  • 0
    F

    Matrix Zigzag Traversal

    Given a matrix:

    [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10, 11, 12]
    ]
    return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

    Solution :

    class Solution {
    public:
        /**
         * @param matrix: a matrix of integers
         * @return: a vector of integers
         */
        vector<int> printZMatrix(vector<vector<int>> &matrix) {
            vector<int> zigzag;
            const int m = matrix.size()-1, n = matrix[0].size()-1;
            for (int i = 0; i <= m + n; ++i) {
                if (i & 1) {
                    for (int x = 0; x <= i; x++) {
                        if ((x <= m) && (i - x <= n)) {
                            zigzag.emplace_back(matrix[x][i-x]);
                        }
                    }
                } else {
                    for (int x = i; x >= 0; x--) {
                        if ((x <= m) && (i-x) <= n) {
                            zigzag.emplace_back(matrix[x][i-x]);
                        }
                    }
                }
            }
            return zigzag;
        }
    };
    

    Sub-Array Sum

    Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

    Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

    Solution

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @return: A list of integers includes the index of the first number
         *          and the index of the last number
         */
        vector<int> subarraySum(vector<int> nums) {
            unordered_map<int, int> table;
            /** the start position **/
            table[0] = -1;
            for (int i = 0, sum = 0; i < nums.size(); ++i) {
                sum += nums[i];
                if (table.find(sum) != table.end()) {  // Already exists.
                    return {table[sum] + 1, i};
                }
                table[sum] = i;
            }
            return {};
        }
    };
    

    So how about extending to matrix ?

    Submatrix Sum

    Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

    class Solution {
    public:
        /**
         * @param matrix an integer matrix
         * @return the coordinate of the left-up and right-down number
         */
        vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
            // Write your code here
            vector<vector<int>> result;
            if (matrix.size() == 0)  return result;
            int rows = matrix.size(), cols = matrix[0].size();
            vector<vector<int>> sum(rows + 1, vector<int>(cols + 1, 0));
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    sum[i+1][j+1] = matrix[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];
                }
            }
            unordered_map<int, int> dict;
            for (int i = 0; i < rows; i++) {
                for (int j = i + 1; j <= rows; j++) {
                    dict.clear();
                    dict[0] = 0;
                    for(int k = 1; k <= cols; k++) {
                        int diff = sum[j][k] - sum[i][k];
                        if(dict.find(diff) != dict.end()) {
                            result.push_back({i, dict[diff]});
                            result.push_back({ j - 1, k - 1});
                            return result;
                        }
                        dict[diff] = k;
                    }
                }
            }
            return result;
        }
    };
    
    

    Maximum Subarray

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @return: A integer indicate the sum of max subarray
         */
        int maxSubArray(vector<int> nums) {
            int max_sum = INT_MIN, sum = 0;
            for (const auto& i : nums) {
                sum += i;
                max_sum = max(max_sum, sum);
                sum = max(sum, 0);
            }
            return max_sum;
        }
    };
    
    

    Minimum Subarray

    Solution

    class Solution {
    public:
        /**
         * @param nums: a list of integers
         * @return: A integer denote the sum of minimum subarray
         */
        int minSubArray(vector<int> nums) {
            int min_sum = INT_MAX, sum = 0;
            for (auto& i : nums) {
                sum += i;
                min_sum = min(min_sum, sum);
                if (sum > 0) {
                    sum = 0;
                }
            }
            return min_sum;
        }
    };
    

    Maximum Subarray 2

    Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.

    For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @return: An integer denotes the sum of max two non-overlapping subarrays
         */
        int maxTwoSubArrays(vector<int> nums) {
            int n = nums.size();
            vector<int> max_LR(n);
            vector<int> max_RL(n);
            int max_LR_sum = INT_MIN, LR_sum = 0;
            for(int i = 0; i < n; i++) {
                LR_sum += nums[i];
                max_LR_sum = max(max_LR_sum, LR_sum);
                max_LR[i] = max_LR_sum;
                LR_sum = max(LR_sum, 0);
            }
            
            int max_RL_sum = INT_MIN, RL_sum = 0;
            for(int i = n - 1; i >= 0; i--) {
                RL_sum += nums[i];
                max_RL_sum = max(max_RL_sum, RL_sum);
                max_RL[i] = max_RL_sum;
                RL_sum = max(RL_sum, 0);
            }
            int max_sum = INT_MIN;
            for(int i = 0; i < n - 1; i++) {
                max_sum = max(max_sum, max_LR[i] + max_RL[i+1]);
            }
            return max_sum;
         }
    };
    
    

    Maximum Subarray 3

    Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

    典型划分类动态规划
    localMax[i][k] 表示前i个数,取k个子数组,包含第i个数的Maximum Sum
    globalMax[i][k] 表示前i个数,取k个子数组,可以不包含第i个数的Maximum Sum
    状态转移方程

    localMax[i][k] = max(localMax[i - 1][k] + nums[i - 1], globalMax[i - 1][k - 1] + nums[i - 1])
    globalMax[i][k] = max(globalMax[i - 1][k], localMax[i][k])

    class Solution {
    public:
    	int maxSubArray(vector<int>& nums, int k) {
    		int n = nums.size();
            vector<vector<long>> local(n+1, vector<long>(k+1, INT_MIN));
            vector<vector<long>> global(n+1, vector<long>(k+1, INT_MIN));
    		for (int i = 0; i < n+1; i++) local[i][0] = global[i][0] = 0;
    		for (int i = 1; i < n+1; i++) {
    		    local[i][0] = global[i][0] = 0;
    			for(int j = 1; j < k+1; j++) {
    				local[i][j] = max(local[i-1][j] + nums[i-1], global[i-1][j-1] + nums[i-1]);
    				global[i][j] = max(global[i-1][j], local[i][j]);
    			}
    		}
    		return global[n][k];
    	}
    };
    
    
    
    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @param k: An integer denote to find k non-overlapping subarrays
         * @return: An integer denote the sum of max k non-overlapping subarrays
         */
        int maxSubArray(vector<int> nums, int k) {
            const int n = nums.size();
    
            // sums[x][y] means the max sum in range [0, x - 1] with k non-overlapping subarrays
            vector<vector<int>> sums(n + 1, vector<int>(k + 1, INT_MIN));
    
            for (int i = 0; i <= n; ++i) {
                sums[i][0] = 0;
            }
    
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= min(i, k); ++j) {
                    sums[i][j] = sums[i - 1][j];
                    int sum = 0, max_sum = INT_MIN;
                    for (int p = i; p > j - 1; --p) {
                        sum += nums[p - 1];
                        max_sum = max(max_sum, sum);
                        sum = max(0, sum);
                        // max sum in range[0, i - 1] with j subarrays equals to
                        // max sum in max(range [0, p - 2] with j - 1 subarrys plus
                        // max sum in range [p - 1, i - 1] with 1 subarray 
                        sums[i][j] = max(sums[i][j], sums[p - 1][j - 1] + max_sum);
                    }
                }
            }
    
            return sums[n][k];
        }
    };
    

    Maximum Sub-Array Difference

    Given an array with integers.Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.Return the largest difference.

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @return: An integer indicate the value of maximum difference between two
         *          Subarrays
         */
        int maxDiffSubArrays(vector<int> nums) {
            int n = nums.size();
            vector<int> max_LR(n), min_LR(n);
            vector<int> max_RL(n), min_RL(n);
    
            // Compute the max sum of subarray from left to right.
            int max_LR_sum = INT_MIN, LR_sum = 0;
            for (int i = 0; i < n; ++i) {
                LR_sum += nums[i];
                max_LR_sum = max(max_LR_sum, LR_sum);
                max_LR[i] = max_LR_sum;
                if (LR_sum < 0) {
                    LR_sum = 0;
                }
            }
    
            // Compute the min sum of subarray from left to right.
            int min_LR_sum = INT_MAX;
            LR_sum = 0;
            for (int i = 0; i < n; ++i) {
                LR_sum += nums[i];
                min_LR_sum = min(min_LR_sum, LR_sum);
                min_LR[i] = min_LR_sum;
                if (LR_sum > 0) {
                    LR_sum = 0;
                }
            }
    
            // Compute the max sum of subarray from right to left.
            int max_RL_sum = INT_MIN, RL_sum = 0;
            for (int i = n - 1; i >= 0; --i) {
                RL_sum += nums[i];
                max_RL_sum = max(max_RL_sum, RL_sum);
                max_RL[i] = max_RL_sum;
                if (RL_sum < 0) {
                    RL_sum = 0;
                }
            }
    
            // Compute the min sum of subarray from right to left.
            int min_RL_sum = INT_MAX;
            RL_sum = 0;
            for (int i = n - 1; i >= 0; --i) {
                RL_sum += nums[i];
                min_RL_sum = min(min_RL_sum, RL_sum);
                min_RL[i] = min_RL_sum;
                if (RL_sum > 0) {
                    RL_sum = 0;
                }
            }
    
            // Compute the max diff of two non-overlapping subarrays.
            int max_diff = 0;
            for (int i = 0; i < n - 1; ++i) {
                max_diff = max(max_diff, abs(max_LR[i] - min_RL[i+1]));
                max_diff = max(max_diff, abs(min_LR[i] - max_RL[i+1]));
            }
    
            return max_diff;
        }
    };
    

    Subarray Sum Closest

    Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

    Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

    Solution :

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @return: A list of integers includes the index of the first number 
         *          and the index of the last number
         */
        vector<int> subarraySumClosest(vector<int> nums){
            // write your code here
            vector<pair<int, int> > acc;
            acc.push_back(make_pair(0, -1));
            int sum = 0;
            for (int i = 0; i < nums.size(); ++i) {
                sum += nums[i];
                acc.push_back(make_pair(sum, i));
            }
            sort(acc.begin(), acc.end());
            int min_abs = INT_MAX, a, b, tmp;
            for (int i = 1; i < acc.size(); ++i) {
                tmp = abs(acc[i].first - acc[i-1].first);
                if (min_abs >= tmp) {
                    min_abs = tmp;
                    a = acc[i-1].second;
                    b = acc[i].second;
                }
            }
            vector<int> res;
            res.push_back(min(a, b) + 1);
            res.push_back(max(a, b));
            return res;
        }
    };
    
    

    Maximum Product Subarray

    class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            if (nums.empty()) return 0;
            int result = nums[0], global_min = nums[0], global_max = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                int local_min = global_min, local_max = global_max;
                global_max = max(max(nums[i], local_max * nums[i]), local_min * nums[i]);
                global_min = min(min(nums[i], local_max * nums[i]), local_min * nums[i]);
                result = max(result, global_max);
            }
            return result;
        }
    };
    

    Continuous Subarray Sum
    Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

    class Solution {
    public:
        /**
         * @param A an integer array
         * @return  A list of integers includes the index of 
         *          the first number and the index of the last number
         */
        vector<int> continuousSubarraySum(vector<int>& A) {
            if (A.empty()) {
                return {-1, -1};
            }
    
            int curr_sum = 0;
            int max_sum = 0;
            vector<int> result{0, 0};
            int start = 0;
            for (int j = 0; j < A.size(); ++j) {
                curr_sum += A[j];
                
                if (curr_sum > max_sum) {
                    max_sum = curr_sum;
                    result[0] = start, result[1] = j;
                }
                
                if (curr_sum < 0) {
                    start = j+1;
                    curr_sum = 0;
                }
            }
    
            return result;
        }
    };
    
    

    Continuous Subarray Sum 2

    Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)
    Example Give [-3, 1, 3, -3, 4], return [1,4].

    class Solution {
    public:
        /**
         * @param A an integer array
         * @return  A list of integers includes the index of
         *          the first number and the index of the last number
         */
        vector<int> continuousSubarraySumII(vector<int>& A) {
            vector<int> result{-1, -1};
            int max_sum = numeric_limits<int>::min();
            int total = 0;
    
            // Non-circular subarray.
            int sum = 0;
            int start = 0, end = 0;
            for (int i = 0; i < A.size(); ++i) {
                total += A[i];
                if (sum < 0) {
                    sum = A[i];
                    start = end = i;
                } else {
                    sum += A[i];
                    end = i;
                }
                if (sum >= max_sum) {
                    max_sum = sum;
                    result[0] = start;
                    result[1] = end;
                }
            }
    
            // Circular subarray.
            sum = 0;
            start = 0, end = -1;
            for (int i = 0; i < A.size(); ++i) {
                if (sum > 0) {
                    sum = A[i];
                    start = end = i;
                } else {
                    sum += A[i];
                    end = i;
                }
                if (total - sum > max_sum && !(start == 0 && end == A.size() - 1)) {
                    max_sum = total - sum;
                    result[0] = (end + 1) % A.size();
                    result[1] = (start - 1) % A.size();
                }
            }
    
            return result;
        }
    };
    

    The key are the following lines :

            curr_sum = 0;
            start = 0, end = -1;
            
            for (int i = 0; i < A.size(); i++) {
                curr_sum += A[i];
                if (total - sum > max_sum && (!(start == 0 && end == A.size() - 1))) {
                    max_sum = total - sum;
                    result[0] = (end + 1) % A.size();
                    result[1] = (start - 1) % A.size();
                }
            }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.