算法：动态规划-填表，最大子数组问题

本文主要是介绍算法：动态规划-填表，最大子数组问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]

输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

此问题为动态规划问题

代码：

时间复杂度为O(n^2)

class Solution {

    public int lengthOfLIS(int[] nums) {

        int len=nums.length;

        int[] dp=new int[len];

        // 1 初始化为1

        for(int i=0;i<len;i++){

            dp[i]=1;

        }

        // 2 填表

        for(int i=0;i<len;i++){

            for(int j=0;j<i;j++){

                if(nums[i]>nums[j]){

                    dp[i]=Math.max(dp[j]+1,dp[i]);

                }

            }

        }

        // 3 遍历dp表，找到最大值

        //因为dp[i]的含义是以第i个元素结尾的最大的递增子序列，所以dp[len-1]不一定最大！

        int max=0;

        for(int i=0;i<len;i++){

            max=Math.max(max,dp[i]);

        }

        return max;

    }

}

 主要思想路为用bp[i]去记录所遍历子数组最大值

时间复杂度为O(n^2)

其为解法的一种，还可以用O(nlog(n)来解，下次填坑。

这篇关于算法：动态规划-填表，最大子数组问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！