给定一个整数数组,找到一个具有最大和的子数组,返回其最大和.
思路一要点:1:设置结果 result 的初始值为无穷小 Integer.MIN_VALUE;
2:只需要一层循环就能完成任务
public class Solution {
/*
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] nums) {
// write your code here
int result=(int)Integer.MIN_VALUE,max,sum=0; for(int i=0;i<=nums.length-1;i++){
if(sum<0)
sum=nums[i];
else
sum+=nums[i];
if(result
result=sum;
}
return result;
}
}
思路二要点:
1:拷贝两个空数组
2:对于序列 - 1,2,求出 2, 和 - 1+2 的最大值,再求出 - 1 和 - 1+2 的最大值,
public int maxSubArray(int[] nums) {
// write your code if (nums==null) return 0; int len = nums.length; int[] a = new int[len]; int[] b = new int[len]; for(int i=0 ;i<len;i++){ if(i==0){ a[i]=b[i]=nums[i]; }else{ a[i]=Math.max(a[i-1]+nums[i],nums[i]); b[i]=Math.max(a[i],b[i-1]); } } return b[len-1]; }
来源: http://www.bubuko.com/infodetail-2471187.html