力扣算法-485-最大连续1的个数-动态规划

485. 最大连续1的个数
给定一个二进制数组， 计算其中最大连续1的个数。

示例 1:

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：

输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。

两种思路，一种是直接遍历，计算最大连续1的个数；一种是动态规划。

思路一、直接遍历
代码：

public int findMaxConsecutiveOnes(int[] nums){

        if(nums == null || nums.length == 0){
            return 0;
        }
        int max_ones = 0;
        if(nums[0] == 1){
            max_ones = 1;
        }else
        {
            max_ones = 0;
        }
        int result = max_ones;
        for(int i = 1;i < nums.length;i++){
            if(nums[i] == 1){
                max_ones++;
            }
            else{
                max_ones = 0;
            }
            result = Math.max(result,max_ones);
        }
        return result;
}

思路二、动态规划
动态规划三要素：初始值、关系式、结束值，中心思想是将问题拆分成可以重复利用的子问题来寻找解。
解体步骤，
代码：

public int findMaxConsecutiveOnes2(int[] nums){

        if(nums == null || nums.length == 0){
            return 0;
        }
        int result = nums[0];
        for(int i = 1;i < nums.length;i++){
            if(nums[i] == 1){
                nums[i] = nums[i-1] + 1;
            }else{
                nums[i] = 0;
            }
            result = Math.max(result,nums[i]);
        }
        return result;
}
以例子nums= [1,1,0,1,1,1]来讲，该方法得到了一个新的数组
nums=[1,2,0,1,2,3]
而返回结果即为新nums中的最大值3

力扣算法-485-最大连续1的个数-动态规划

原文：https://www.cnblogs.com/mengriver/p/14403537.html