首页 > 代码库 > Leetcode 53. Maximum SubarrayJAVA语言
Leetcode 53. Maximum SubarrayJAVA语言
Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
题意:求连续子数组的最大和
public class Solution { public int maxSubArray(int[] nums) { int len=nums.length; if(nums==null || len==0)return 0; int MAX=nums[0]; int curSum=nums[0]; for(int i=1;i<len;i++){ if(curSum>0){ curSum+=nums[i]; }else{ curSum=nums[i]; } MAX=Math.max(curSum,MAX); } return MAX; } }
PS:第一种思路,逐渐累加循环。
还有一种思路,可以用动态规划做。
public class Solution { public int maxSubArray(int[] nums) { int len=nums.length; if(nums==null || len==0)return 0; //dp[i]代表以nums[i]为结尾的最大和。 int[] dp=new int[len]; dp[0]=nums[0]; int MAX=dp[0]; for(int i=1;i<len;i++){ if(dp[i-1]<0){ dp[i]=nums[i]; }else{ dp[i]=dp[i-1]+nums[i]; } MAX=Math.max(dp[i],MAX); } return MAX; } }
Leetcode 53. Maximum SubarrayJAVA语言
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。