请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

【LeetCode: 1911. 最大子序列交替和 | 暴力递归=>记忆化搜索=>动态规划 】

2023-07-13

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述
在这里插入图片描述

🚩 题目链接

⛲ 题目描述

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。

比方说,数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。
给你一个数组 nums ,请你返回 nums 中任意子序列的 最大交替和 (子序列的下标 重新 从 0 开始编号)。

一个数组的 子序列 是从原数组中删除一些元素后(也可能一个也不删除)剩余元素不改变顺序组成的数组。比方说,[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列(加粗元素),但是 [2,4,2] 不是。

示例 1:

输入:nums = [4,2,5,3]
输出:7
解释:最优子序列为 [4,2,5] ,交替和为 (4 + 5) - 2 = 7 。
示例 2:

输入:nums = [5,6,7,8]
输出:8
解释:最优子序列为 [8] ,交替和为 8 。
示例 3:

输入:nums = [6,2,1,2,4,5]
输出:10
解释:最优子序列为 [6,1,5] ,交替和为 (6 + 5) - 1 = 10 。

提示:

1 <= nums.length <= 105
1 <= nums[i] <= 105

🌟 求解思路&实现代码&运行结果


⚡ 暴力法

🥦 求解思路

  1. 简单概括题目的意思:这是一道子序列类型的题目,每个位置可以选择,也可以不选,让我们求得nums数组中任意子序列的最大交替和。(最大交替和的定义请看题目)
  2. 具体怎么求解呢?我们对题目进行一个拆分,发现最终求解的问题规模是可以转换为更小的问题规模进行求解的,所以我们通过递归的思路来求解。
  3. 问题又来了?怎么设计递归函数呢?这个就需要大家认真考虑了。
  4. 我们假设定义递归函数process(index,flag),函数的含义是从index位置开始,flag=0代表此时已经选择了偶数个数,flag=1则相反,最终返回最大交替和。
  5. 具体的状态是怎么转移的呢?我们可以分为以下俩种情况:如果当前选择了偶数个数,那么此时有俩种可能,可以之前并没有选择;也有可能是之前选择了奇数个数并且选择当前的数,俩者去较大值即可;同理可以推出如果选择了奇数个数的情况,最终再取得俩种情况的最大值即可。
  6. 有了基本的思路,接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {

    int[] nums;
    int n;

    public long maxAlternatingSum(int[] nums) {
        n=nums.length;
        this.nums=nums;
        return process(0,0);
    }

    public long process(int index,int cnt){
        if(index>=n) return 0;
        long p1=0,p2=0;
        if(cnt==0){
            p1=Math.max(process(index+1,0),process(index+1,1)+nums[index]);
        }else{
            p2=Math.max(process(index+1,1),process(index+1,0)-nums[index]);
        }
        return Math.max(p1,p2);
    }
}

🥦 运行结果

时间复杂度&空间复杂度

在这里插入图片描述


⚡ 记忆化搜索

🥦 求解思路

  1. 因为在递归的过程中,会重复的出现一些多次计算的结果,我们通过开辟一个数组,将结果提前缓存下来,算过的直接返回,避免重复计算,通过空间来去换我们的时间。

🥦 实现代码

class Solution {

    int[] nums;
    int n;
    long[][] map;

    public long maxAlternatingSum(int[] nums) {
        n=nums.length;
        this.nums=nums;
        map=new long[n+1][2];
        for(int i=0;i<=n;i++){
            for(int j=0;j<2;j++){
                map[i][j]=-1;
            }
        }
        return process(0,0);
    }

    public long process(int index,int cnt){
        if(index>=n) return 0;
        if(map[index][cnt]!=-1) return map[index][cnt];
        long p1=0,p2=0;
        if(cnt==0){
            p1=Math.max(process(index+1,0),process(index+1,1)+nums[index]);
        }else{
            p2=Math.max(process(index+1,1),process(index+1,0)-nums[index]);
        }
        map[index][cnt]=Math.max(p1,p2);
        return map[index][cnt];
    }
}

🥦 运行结果

通过缓存,将重复计算的结果缓存下来,通过。

时间复杂度&空间复杂度
在这里插入图片描述


⚡ 动态规划

🥦 求解思路

  1. 有了递归,有了记忆化搜索,接下来就是动态规划了,直接上手。

🥦 实现代码

class Solution {

    int[] nums;
    int n;
    long[][] dp;

    public long maxAlternatingSum(int[] nums) {
        this.n=nums.length;
        this.nums=nums;
        dp=new long[n+1][2];
        dp[n][0]=dp[n][1]=0;
        for(int index=n-1;index>=0;index--){
            dp[index][0]=Math.max(dp[index+1][0],dp[index+1][1]+nums[index]);
            dp[index][1]=Math.max(dp[index+1][1],dp[index+1][0]-nums[index]);
        }
        return dp[0][0];
    }
}

🥦 运行结果

动态规划搞定,大家可以积极的尝试。

时间复杂度&空间复杂度

在这里插入图片描述

扩展:还可以继续进行优化算法的空间复杂度


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部