算法经典面试题(手撕腾讯面试题)

前言

动态规划是面试中常考的知识点,特别是一些互联网大厂的面试,可以说必会考到一道涉及动态规划的算法题,因此掌握动态规划,能提高面试的通过率。

本文的内容为通过一道腾讯的面试题,即力扣 152. 乘积最大子数组,由暴力法求解一步一步演化到由动态规划进行求解来介绍动态规划

题目

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

示例

算法经典面试题(手撕腾讯面试题)(1)

解题思路

注意点

本题要求的是乘积最大的连续子数组而不是乘积最大的子序列,因此要求子数组中的元素在原数组中是连续的

思考:整数数组可能存在的情况

由于题目已明确告知子数组中至少包含一个数字,因此主要存在以下两种情况:

整数数组 nums 中只包含一个元素;

整数数组 nums 中包含两个或两个以上元素。

思路

只包含一个元素,直接返回该元素;

包含两个或两个以上元素,暴力轮询或动态规划求乘积最大的连续子数组,返回乘积。

暴力法

初看该题,很容易想到可以通过暴力法去求解,即通过两层循环遍历整个数组。

Show me the Code

C

算法经典面试题(手撕腾讯面试题)(2)

上面是通过暴力法去求解,由于进行了两层遍历,因此该解法的时间复杂度O(n^2),但由于未开辟额外的空间,所以空间复杂度O(1)。但在面试过程中,如果提供这种解法,面试官往往会问还有没有更优的解法?也就是说面试官对当前的解法(时间复杂度过高)不太满意。

那有没有更优的解法呢?当然有!对动态规划有所了解的童鞋,在看到题目中的最大两个字,自然会想到通过动态规划去求解,因为涉及到求最优的问题,往往可以通过动态规划去解。

动态规划

由于整数数组 nums 中的元素可能有正数、负数和 0,因此连续子数组中的元素也可能是这三种情况

如果连续子数组中的元素存在负数正数乘以负数就成负数,那么最大值乘以负数就变成了最小值,因此需要同时考虑当前连续子数组乘积的最大值curMax最小值curMin

注意点

整数数组 nums 中存在负数,当遍历到以nums[i](负数)结尾连续子数组时,需要交换 curMax 和 curMin

举栗

以整数数组nums = [2, 3, -2, 4]为栗子,求乘积最大子数组的乘积。

如下图示

算法经典面试题(手撕腾讯面试题)(3)

代码示例:

C

算法经典面试题(手撕腾讯面试题)(4)

C语言

算法经典面试题(手撕腾讯面试题)(5)

采用动态规划的方法去求解,由于只进行了一层遍历,因此其时间复杂度O(n),同样由于未开辟额外的空间,所以空间复杂度O(1)

今天的分享就到这里了,大家要好好学C 哟~

写在最后:对于准备学习C/C 编程的小伙伴,如果你想更好的提升你的编程核心能力(内功)不妨从现在开始!

编程学习书籍分享:

算法经典面试题(手撕腾讯面试题)(6)

编程学习视频分享:

算法经典面试题(手撕腾讯面试题)(7)

整理分享(多年学习的源码、项目实战视频、项目笔记,基础入门教程)

欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!

对于C/C 感兴趣可以关注小编在后台私信我:【编程交流】一起来学习哦!可以领取一些C/C 的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页