41. 最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

思路一要点：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<sum)
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]; }