summary of Maximum Subarray & Maximum Product Subarray


  • 4
    F

    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;
        }
    };
    

    Maximum Subarray

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if (nums.empty()) return 0;
            int global = nums[0];
            int local = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                local = max(nums[i], local + nums[i]);
                global = max(global, local);
            }
            return global;
        }
    };

  • 0
    R

    Nice summary!


Log in to reply
 

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