LeetCode——最大子序和 发表于 2020-03-14 更新于 2020-03-16 分类于 题解笔记 阅读次数: Valine: 本文字数: 361 NO.53 最大子序和 简单 思路一:动态规划法 分析dp那就要先分析dp[i]的含义:以第i元素结尾的最大序列和。 初始化:dp[0]以第0号元素结尾的序列只有nums[0]本身,所以dp[0]=nums[0]。 转移方程:dp[i]=Max(dp[i-1]+nums[i],nums[i]),因为dp[i-1]是以i-1为结尾的序列和中的最大值,所以我们想找nums[i]结尾的最大序列和只需要比较”前一个最大序列和+nums[i]”和”nums[i]”。举个例子: 12345678910111213public int maxSubArray(int[] nums) { if (nums==null||nums.length==0)return 0; int[] dp=new int[nums.length]; //初始化 dp[0]=nums[0]; //填写dp数组同时用max记录当前最大的序列和 int max=dp[0]; for (int i = 1; i < nums.length; i++) { dp[i]=Math.max(nums[i],dp[i-1]+nums[i]); max=Math.max(max,dp[i]); } return max;} 经过思考不难发现,并不需要开辟一个数组来保存每一个子序和。每次填写只需要关心上一次状态值即可,且每个状态值只需要使用一次。所以我们可以用一个int变量代替dp数组即可: 123456789101112public int maxSubArray(int[] nums) { if (nums==null||nums.length==0)return 0; //初始化 int dp=nums[0]; //更新当前i结尾的最大序列和同时用max记录最大的序列和 int max=dp; for (int i = 1; i < nums.length; i++) { dp=Math.max(nums[i],dp+nums[i]); max=Math.max(max,dp); } return max;} 时间复杂度:O(n) 本人菜鸟,有错误请告知,感激不尽! 更多题解和学习记录博客:博客、github