2023华为OD面试手撕真题【最大子数组和】

小灰灰 2024-02-05 15:57 8阅读 0赞

这个题目是leetcode 53的原题，老样子，面试官直接让打开leetcode，直接在leetcode上做题，并提交检查通过率。题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

> 给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
> 
> **子数组** 是数组中的一个连续部分。
> 
> **示例 1：**
> 
>     输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
>     输出：6
>     解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
> 
> **示例 2：**
> 
>     输入：nums = [1]
>     输出：1
> 
> **示例 3：**
> 
>     输入：nums = [5,4,-1,7,8]
>     输出：23s

说实话这个题目还是非常经典的，**题目短小描述简单，并且解法众多，各种解法从简到难，非常适合作为面试手撕出题**。老样子，先说结论：

1：拿到题目先想几分钟，不要急于写下代码。

2：一般面试手撕题目的解法会比较多，不用纠结于最佳解法，暴力能做出正确的解一般也能满足面试官的要求。

3：实在想不出来，可以申请换题。

4：面试官有可能会问各种解法对应的时间空间复杂度，这个要重点注意。

回到这个题目上来，子数组类的题目。一般都会有暴力、动态规划、滑动窗口等几种经典解法。我们拿到题目可以直接往这几种解法上靠，分别思考一下是否能套用上这个写法。**避免拿到题目，大脑一片空白的情况出现**。【**这个问题群里很多小伙伴都提到过，这个方法可以尽量的缓解这个问题**】

![515475aba94c43c19989ad1634539842.png][]

我自己尝试写了一些解答，但是看了一下网上一些大佬写的文章，自愧不如，这里直接贴出来我觉得写的比较好的一个大佬的文章吧，这篇文章也作为试读的文章，免费给大家看了：

[LeetCode 一题多解 | 53. 最大子数组和：五种解法完全手册-CSDN博客][LeetCode _ _ 53. _-CSDN]

[LeetCode_ -]: https://leetcode.cn/problems/maximum-subarray/
[515475aba94c43c19989ad1634539842.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/2184fb864ad248b4956d54c45a247c44.png
[LeetCode _ _ 53. _-CSDN]: https://blog.csdn.net/kexuanxiu1163/article/details/107624973