[Java] Sliding Window and DP solution


  • 0

    Sliding window solution

    public int findMaxConsecutiveOnes(int[] nums) {
            int n = nums.length;
            if(n == 0) return 0;
            int left = 0, right = 0, zero = 0, k = 1, max = 0;
            while(right < n){
                if(nums[right] == 0) zero ++;
                while(zero > k){
                    if(nums[left ++] == 0) zero --;
                }
                max = Math.max(max, right - left + 1);
                right ++;
            }
            return max;
        }
    

    DP solution

    public int findMaxConsecutiveOnes(int[] nums) {
            int n = nums.length;
            if(n == 0) return 0;
            int[] dp = new int[n];
            dp[0] = nums[0] == 1 ? 1 : 0;
            for(int i = 1; i < n; i ++){
                dp[i] = nums[i] == 1 ? dp[i - 1] + 1 : 0;
            }
            int max = 0;
            for(int i = 0; i < n; i ++){
                int cur = dp[i];
                if(i - dp[i] == 0) cur += 1;
                else if(i - dp[i] - 1 >= 0) cur += dp[i - dp[i] - 1] + 1;
                max = Math.max(max, cur);
            }
            return max;
        }
    

Log in to reply
 

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