Simple Dynamic Programming Problem [Accepted]


  • 0
    B

    Algorithm
    We use the dp[i] to keep the numbers of consecutive 1s ending with nums[i].
    There is two cases:

    • if nums[i] == 1, then dp[i] = dp[i-1] + 1.
    • if nums[i] == 0, then dp[i] = 0.
      First, we traverse the given array to generate the dp array;
      then, we find the max element of dp array and return.

    Java

    class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            int [] dp = new int[nums.length];
            if(nums[0] == 1){
                dp[0] = 1;
            }else {
                dp[0] = 0;
            }
            for(int i = 1; i <nums.length; i++){
                if(nums[i] == 1){
                    dp[i] = dp[i - 1] + 1;
                }else {
                    dp[i] = 0;
                }
            }
            int result = 0;
            for(int i = 0; i < dp.length; i++){
                if(dp[i] > result){
                    result = dp[i];
                }
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n). We traverse the nums of size n once, and then traverse the dp array of size n once. Here, n refer to the number of elements in the given array.
    • Space complexity : O(n). The dp array of size n is used.

Log in to reply
 

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