哈喽大家好，这里是万诺工作室，接下来将会陆续推出一系列关于面试的时候常见的手撕代码的题目，欢迎大家交流！
一、题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
二、 题目解析
a.暴力解法
很多没有经验的同学看到这道题的最直观的做法就是，暴力解法。所谓暴力解就是不管不顾，把所有可能出现的情况遍历一次，再用一个变量记录最优值。这种做法固然不错，特别是没有时间复杂度的笔试题，大部分情况是可以AC的。但是这也是面试官最不愿看到的，相信很多同学会有这样的经验，面试的题目把笔试题目拿出来让你再重新做一次……
由于暴力解法不是最好的方法，这里就仅仅是展示一下思路，不把代码写出来。
所谓的暴力，就是不管不顾，把所有可能发生的情况的列举出来，不管会不会重复计算，反正我只要可以算出结果就行了。具体思路是：寻找所有的可能组成的子序列，求得最大值，实现只需要两个for循环即可，代码实现也比较简单，但是时间复杂度达到了可怕的O(n^2)。
b.动态规划
这道题目的解法有很多，贪心和分治都可以，但是效率最高的也就是我们这篇文章要讲解的动态规划。
动态规划是什么意思呢？百度的解释是这样的：
有一种来自一本日本的程序设计书籍中的说法我比较赞同，因为对于初学者比较好理解：动态规划就是记录结果再利用。也就是说，一些结果我们在计算过程中是会遇到不止一次的，那我们不需要每次遇到都去重新算一次，而是从我们存下来的数据里面去拿。这样说可能还不好理解，举个最简单的例子：
斐波那契数列：1,1,2,3,5,8,13,21……，求f(n)。递归式显而易见：f(n) = f(n-1)+f(n-2)那代码也很容易写出来：fib(n):ifn==1:return1;ifn==2:return1;else:returnfib(n-2)+fib(n-1);
但这不是最好的方式，如图所示，会有大量的重复的子结果并且会进行大量重复的运算，当我们的n一大的时候，复杂度可想而知。
所以解决方案就是把每一个子结果都记录下来，后续有需要用的直接调用即可，不需要继续递归计算。这也就是一种动态规划的思想。
好像有点跑题了，言归正传。
那这道题要怎么做呢？首先动态规划我们是需要找出状态转移方程式，也就是从当前状态转移到另一个状态的一个等式。对于这道题来说，我们先设置一个状态dp[i]表示到第i个数的最大子序列的和，所以对于dp[i-1]来说，到了第i位，之前的最长的子序列只有两种情况，要么把第i位跟之前的子序列加上，要么把第i位当作新的起点。因此状态转移方程式就是：
dp[i]= max(dp[i-1]+nums[i],nums[i])
只要理解了这个方程式，写出代码来就是分分钟的事情了。
那这里就把代码简单的贴一下：
classSolution{publicintmaxSubArray(int[] nums){//dp[i]表示以第i个数结尾的最大子序列的和//dp[i] = max(dp[i-1]+nums[i],nums[i])int[] dp =newint[nums.length];intres = nums[0];dp[0] = nums[0];for(inti=1;i
从代码就看的出来，这种方式只需要进行一次遍历就可以得到结果，也就是说时间复杂度是O(n)。什么概念呢？下面贴一张O(n^2)和O(n)的时间增长对比，那就知道当我们的基数增大的时候，运算所使用的时间将会产生巨大的差别。所以啊，慎用暴力！
关注万诺工作室，持续输出对你有用的干货！
网友评论