9ms C++ divide and conquer solution


  • 0
    C
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if (nums.size() == 0) {
                return 0;
            }
            ReturnType ret = helper(nums, nums.size()-1);
            return ret.maxOverall_;
        }
    private:
        class ReturnType {
        public:
            int maxEndHere_;
            int maxOverall_;
        };
        
        ReturnType helper(vector<int>& nums, int n) {
            ReturnType ret;
            if (n == 0) {
                ret.maxEndHere_ = nums[0];
                ret.maxOverall_ = nums[0];
                return ret;
            }
            ret = helper(nums, n-1);
            ret.maxEndHere_=max(ret.maxEndHere_+nums[n], nums[n]);
            ret.maxOverall_=max(ret.maxEndHere_, ret.maxOverall_);
            return ret;
        }
        
    };
    

Log in to reply
 

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