C++, Divide and Conquer approach solution


  • 0
    Z

    Inspired by this post of the "Maximum Subarray" problem.

    class Solution {
    public:
        int findMaxConsecutiveOnes(vector<int>& nums) {
            return findMax(nums, 0, nums.size());
        }
        
        int findMax(vector<int>& nums, int begin, int end) {
            if(begin >= end)    return 0;
            int mid = (begin + end) >> 1, left = mid, right = mid + 1, curr_len = 0;
            if(nums[mid]) {
                for(; left >= begin; --left) {
                    if(nums[left]) ++curr_len;
                    else    break;
                }
                for(; right < end; ++right) {
                    if(nums[right]) ++curr_len;
                    else    break;
                }
                if(curr_len > mid)  return curr_len;
            }
            return max(max(findMax(nums, begin, left), findMax(nums, right, end)), curr_len);
        }   
    };
    

Log in to reply
 

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