(java)Maximum Subarray

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

.

思路:还是典型的贪心，设置一个maxsum和sum，循环遍历这个数组，当maxsum <sum时，maxsum=sum；

当sum<0 时，将前面的丢弃，sum=0，重新开始；

注意边界nums[i]都是小于0的，返回那个最大的数。

代码如下(已通过leetcode)

public class Solution {

   public int maxSubArray(int[] nums) {

    boolean flag=true;

    int j=0;

    int temp=-Integer.MIN_VALUE;

    while(j<nums.length){

    if(nums[j]>0){

    flag=false;

    break;

    }

    if(nums[j]>temp) temp=nums[j];

    j++;

    }

    if(flag) return temp;

       int sum=0;

       int maxsum=0;

       for(int i=0;i<nums.length;i++){

        sum=sum+nums[i];

        if(sum>maxsum) maxsum=sum;

        if(sum<0) sum=0;

       }

       return maxsum;

   }

}