LeetCode之最值问题系列问题求解

最值系列题目求解

这类型题目的特点就是一个数组，或者字符串， 给的条件是连续或者不连续，或者给定限定条件进行求解的情况

解题的关键

1. 采用两个变量
   • 一个变量记录前面的条件，或者最后一个不满足题意的index，或者最小值, 比如股票题目当中j ,或者最大不重复字符串
   • 一个变量代表截止到处理到该位置处的最大结果值
2. 动态规划保存前面的计算结果，全局变量保存计算结果

利益最大买卖股票

只能进行一次买卖的基本情况

class Solution {
   
    public int maxProfit(int[] prices) {
   
        // 动态规划问题
        if(prices==null||prices.length<2)
            return 0;
        int max = 0;
      //  int i = 0;
        int j = prices[0];
        for(int i=1;i<prices.length;i++){
   
            //有一个基准
            // 最小值更新, 记录最小的买入位置
            j = Math.min(j,prices[i]);
         max =Math.max(prices[i]-j,max);
        }
        return max;
    }
}

最长递增子序列

可以间隔处理
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

解法一：动态规划

时间复杂度为O(N*N)

class Solution {
   
    public int lengthOfLIS(int[] nums) {
   
       int n = nums.length;
        if(n==0) return 0;
        if(n==1) return 1;
        int max = 1;
        int [] dp =new int[n];
        Arrays.fill(dp,1);
        dp[0] =1;
        for(int i=1;i<n;++i){
   
            for(int j=i-1;j>=0;--j)
            {
   
                if(nums[j]<nums[i])
                {
   
                    //因为要求一个增长序列，u=
                   // 状态转移方程dp[i]在前面选择一个num[j]<nums[i],总多条件中选择一个·满足题意的max 的j,然后加i
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
                //如果一个元素找不到一个比他任何一个比他小的元素，那么以这个元素为nums[i] 为尾巴的增长序列只能为1，自己本身
                }
            max = Math.max(max,dp[i]);
        }
        return max;
    }