Java教程

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

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

题目:给你一个整数数组 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)来解,下次填坑。

 

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