【动态规划】剑指 Offer 42. 连续子数组的最大和（简单）
让我们先来看看这道题目的描述
关于这道题目，因为连续两字出现，我们不由得想到了前缀和，先不考虑题目要求的时间复杂度的限制
方法一：前缀和
class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];for(int i = 1; i <= n; ++i){dp[i] = dp[i - 1] + nums[i - 1];}int max = nums[0];for(int i = 0; i < n; ++i){for(int j = i + 1; j <= n; ++j){max = Math.max(max, dp[j] - dp[i]);}}return max;}}
提交发现会TLE，让我们再来给出一个时间复杂度为O（n）的答案
方法二：动态规划
这道题目属于动态规划中比较简单的题目
我们用dp[i]来表示以第i个数结尾的子串的最大和，所以代码就很显然了
class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int max = dp[0];for(int i = 1; i < n; ++i){dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);max = Math.max(max, dp[i]);}return max;}}
这道题目属于动态规划中简单的范畴，比如子串子序列这种类型的动态规划，一定要轻松拿下～
2022秋招马上就要开始了，你刷了多少题呢？