【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列

简介: 【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【动态规划】,使用【数组】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。

连续子数组的最大和【MID】

来从动态规划最简单的题开始训练

题干

题干中可以提炼的关键信息:连续的子数组,整数有正有负,求连续子数组的最大和,题目要我们找出和最大的连续子数组的值是多少,「连续」是关键字,连续很重要,不是子序列。题目只要求返回结果,不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决

解题思路

按照动态规划的思路进行状态设计和状态转移方程编写

1 定义状态(定义子问题)

dp[i]:表示以 nums[i] 结尾的连续子数组的最大和。说明:「结尾」和「连续」是关键字。

2 状态转移方程(描述子问题之间的联系)

根据状态的定义,由于 nums[i] 一定会被选取,并且以 nums[i] 结尾的连续子数组与以 nums[i - 1] 结尾的连续子数组只相差一个元素 nums[i] 。假设数组 nums 的值全都严格大于 0,那么一定有 dp[i] = dp[i - 1] + nums[i]。可是 dp[i - 1] 有可能是负数,于是分类讨论:

  • 如果 dp[i - 1] > 0,那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面,得到和更大的连续子数组;
  • 如果 dp[i - 1] <= 0,那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」,此时单独的一个 nums[i] 的值,就是 dp[i]。

以上两种情况的最大值就是 dp[i] 的值,写出如下状态转移方程:

3 初始化状态

dp[0] 根据定义,只有 1 个数,一定以 nums[0] 结尾,因此 dp[0] = nums[0]

4 求解方向

这里采用自底向上,从最小的状态开始求解

5 找到最终解

这里的dp[i]只是以i为结尾的连续子数组的最大和,并不是题目中的问题,数组的连续子数组最大和,所以最终解并不是子问题的解,需要用一个MAX值承载,通过与dp[i]比较更新最终解

代码实现

给出代码实现基本档案

基本数据结构数组

辅助数据结构

算法动态规划

技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        // 1 定义dp数组,初始化状态,初始化最终解
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int greatSum = dp[0];
        // 2 定义状态转移方程
        for (int i = 1; i < array.length; i++) {
            // 状态转移方程,求解当前的dp[i]
            dp[i] = dp[i - 1] <= 0 ? array[i] : dp[i - 1] + array[i];
            // 更新最大值
            greatSum = Math.max(greatSum, dp[i]);
        }
        return greatSum;
    }
}

复杂度分析

时间复杂度:遍历了一遍数组,所以时间复杂度为O(N)

空间复杂度:定义了动规数组,空间复杂度为O(N)

乘积最大子数组【MID】

处理一个合连续子数组的最大和类似的题目,乘积最大的子数组

题干

解题思路

原题解地址,数组的动态规划问题、子序列、连续子序列的一个常见的状态定义是:

以下标 i 结尾的连续子序列的乘积的最大值。

最后把整个 dp 数组看一遍求最大值即可。因此状态转移方程可能是:

dp[i] = max(dp[i - 1] * nums[i], nums[i])

说明:牢记状态的定义,一定以下标 i 结尾,即:乘积数组中 nums[i] 必须被选取,但是nums[i]可能是正数也可能是负数

  • 如果nums[i] 是负数,要想获得最大乘积,则dp[i-1]越小则dp[i]越大,于是我们可能就需要记录一下**dp[i-1]**的那个最小数。
  • 如果nums[i] 是正数,则取上一个状态的最大值*

所以要维护两个动态规划数组

1 定义状态(定义子问题)

maxDp[i]:表示以 nums[i] 结尾的连续子数组的最大乘积。说明:「结尾」和「连续」是关键字。

minDp[i]: 表示以 nums[i] 结尾的连续子数组的最小乘积。说明:「结尾」和「连续」是关键字。

2 状态转移方程(描述子问题之间的联系)

if (nums[i] >= 0) {
      // 如果当前值为正数,则最大值为 Math.max(nums[i], maxDp[i - 1] * nums[i]),因为maxDp[i-1]可能为负数,这样不如舍弃重新开始
       maxDp[i] = Math.max(nums[i], maxDp[i - 1] * nums[i]);
      // 同时需要更新最小值,nums[i]为正值,所以就用最小乘积,minDp[i - 1] * nums[i]更小
      minDp[i] = Math.min(nums[i], minDp[i - 1] * nums[i]);
} else {
    // 如果当前值为负数,则最大值为Math.max(nums[i], minDp[i - 1] * nums[i]),minDp[i - 1]可能为负数,这样不如使用minDp[i - 1] * nums[i],
    maxDp[i] = Math.max(nums[i], minDp[i - 1] * nums[i]);
    // 同时需要更新最小值,nums[i]为负值,所以就用最大乘积,maxDp[i - 1] * nums[i]更小
    minDp[i] = Math.min(nums[i], maxDp[i - 1] * nums[i]);
 }

3 初始化状态

// base case 初始状态为数组的第一个元素
maxDp[0] = nums[0];
minDp[0] = nums[0];
int ans =  nums[0];

4 求解方向

这里采用自底向上,从最小的状态开始求解

5 找到最终解

最终解采用实时更新的方式

// 更新整体最大值
ans = Math.max(ans, maxDp[i]);

代码实现

给出代码实现基本档案

基本数据结构数组

辅助数据结构

算法动态规划

技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int maxProduct(int[] nums) {
        // 1 入参合法性判断
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 2 定义两个动态规划数组,分别记录以i为结尾的最大乘积子数组,并维护最大乘积值
        int[] maxDp = new int[nums.length];
        int[] minDp = new int[nums.length];
        // 3 base case 初始状态为数组的第一个元素
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int ans =  nums[0];
        // 4 状态转移方程
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                // 如果当前值为正数,则最大值为 Math.max(nums[i], maxDp[i - 1] * nums[i]),因为maxDp[i-1]可能为负数,这样不如舍弃重新开始
                maxDp[i] = Math.max(nums[i], maxDp[i - 1] * nums[i]);
                // 同时需要更新最小值,nums[i]为正值,所以就用最小乘积,minDp[i - 1] * nums[i]更小
                minDp[i] = Math.min(nums[i], minDp[i - 1] * nums[i]);
            } else {
                // 如果当前值为负数,则最大值为Math.max(nums[i], minDp[i - 1] * nums[i]),minDp[i - 1]可能为负数,这样不如使用minDp[i - 1] * nums[i],
                maxDp[i] = Math.max(nums[i], minDp[i - 1] * nums[i]);
                // 同时需要更新最小值,nums[i]为负值,所以就用最大乘积,maxDp[i - 1] * nums[i]更小
                minDp[i] = Math.min(nums[i], maxDp[i - 1] * nums[i]);
            }
            // 更新整体最大值
            ans = Math.max(ans, maxDp[i]);
        }
        return ans;
    }
}

复杂度分析

时间复杂度:遍历了一遍数组,所以时间复杂度为O(N)

空间复杂度:定义了动规数组,空间复杂度为O(N)

最长递增子序列【MID】

终于又来到一道看了很久的高频题目这里

题干

注意「子序列」和「子串」这两个名词的区别,子串一定是连续的,而子序列不一定是连续的

解题思路

按照动态规划的思路进行状态设计和状态转移方程编写,这里用数学归纳法进行状态转移公式的推导。

数学归纳法:比如我们想证明一个数学结论,那么我们先假设这个结论在 k < n 时成立,然后根据这个假设,想办法推导证明出 k = n 的时候此结论也成立。如果能够证明出来,那么就说明这个结论对于 k 等于任何数都成立

我们设计动态规划算法,不是需要一个 dp 数组吗?我们可以假设 dp[0...i-1] 都已经被算出来了,然后问自己:怎么通过这些结果算出 dp[i]

1 定义状态(定义子问题)

我们的定义是这样的:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度,这个定义中 nums[i] 必须被选取,且必须是这个子序列的最后一个元素;

2 状态转移方程(描述子问题之间的联系)

算法演进过程中每个 dp[i] 的结果是我们肉眼看出来的,我们应该怎么设计算法逻辑来正确计算每个 dp[i] 呢?这就是动态规划的重头戏,如何设计算法逻辑进行状态转移,才能正确运行呢?这里需要使用数学归纳的思想:

假设我们已经知道了 dp[0…4] 的所有结果,我们如何通过这些已知结果推出 dp[5] 呢

根据刚才我们对 dp 数组的定义,现在想求 dp[5] 的值,也就是想求以 nums[5] 为结尾的最长递增子序列

nums[5] = 3既然是递增子序列,我们只要找到前面那些结尾比 3 小的子序列,然后把 3 接到这些子序列末尾,就可以形成一个新的递增子序列,而且这个新的子序列长度加一

  • nums[5] 前面有哪些元素小于 nums[5]?这个好算,用 for 循环比较一波就能把这些元素找出来。
  • 以这些元素为结尾的最长递增子序列的长度是多少?回顾一下我们对 dp 数组的定义,它记录的正是以每个元素为末尾的最长递增子序列的长度

以我们举的例子来说,nums[0]nums[4] 都是小于 nums[5] 的,然后对比 dp[0] 和 dp[4] 的值,我们让 nums[5] 和更长的递增子序列结合,得出 dp[5] = 3

for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

3 初始化状态

根据这个定义,我们就可以推出 base case:dp[i] 初始值为 1,因为以 nums[i] 结尾的最长递增子序列起码要包含它自己

4 求解方向

这里采用自底向上,从最小的状态开始求解

5 找到最终解

根据这个定义,我们的最终结果(子序列的最大长度)应该是 dp 数组中的最大值

int res = 0;
for (int i = 0; i < dp.length; i++) {
    res = Math.max(res, dp[i]);
}
return res;

代码实现

给出代码实现基本档案

基本数据结构数组

辅助数据结构

算法动态规划

技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
class Solution {
    // 最长上升子序列
    public int lengthOfLIS(int[] nums) {
        // 1 入参校验判断
        if (nums.length < 1) {
            return -1;
        }
        // 2 定义DP数组:dp[i]表示以nums[i]为结尾的上升子序列的最大长度
        int[] dp = new int[nums.length];
        // 3 base case, 所有元素都至少包含自己,且dp[0]=1 因为只有一个元素,二者合并
        Arrays.fill(dp, 1);
        // 4 状态转移,填充状态转移表
        for (int i = 1; i < nums.length; i++) {
            // dp[i]为i之前的小于nums[i]的所有dp[i]的最大值组成
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 5 最终解为dp数组的最大值
        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

当然最值的更新也可以在双重循环中同步进行

import java.util.*;
class Solution {
    // 最长上升子序列
    public int lengthOfLIS(int[] nums) {
        // 1 入参校验判断
        if (nums.length < 1) {
            return -1;
        }
        // 2 定义DP数组:dp[i]表示以nums[i]为结尾的上升子序列的最大长度
        int[] dp = new int[nums.length];
        // 3 base case, 所有元素都至少包含自己,且dp[0]=1 因为只有一个元素,二者合并
        Arrays.fill(dp, 1);
        // 4 状态转移,填充状态转移表
        int result = 1;
        for (int i = 1; i < nums.length; i++) {
            // dp[i]为i之前的小于nums[i]的所有dp[i]的最大值组成
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

复杂度分析

时间复杂度:O(N^2),这里 N 是数组的长度,我们写了两个 for 循环,每个 for 循环的时间复杂度都是线性的;

空间复杂度:O(N),要使用和输入数组长度相等的状态数组,因此空间复杂度是 O(N)。

相关文章
|
29天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
168 80
|
3天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
27 5
|
22天前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。
|
2月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
71 2
|
2月前
|
算法 C# 索引
C#线性查找算法
C#线性查找算法!
|
3月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
90 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
6天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
6天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
101 68
|
16天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
17天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真