首页 > 代码库 > Maximum Subarray

Maximum Subarray

2024-07-21 16:13:41   220人阅读

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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

答案

public class Solution {
    public int maxSubArray(int[] A) {
        if(A==null||A.length<1)
        {
            return 0;
        }
        int result=A[0];
        int current=A[0];
        int LEN=A.length;
        for(int i=1;i<LEN;i++)
        {
            current=Math.max(A[i],current+A[i]);
            result=Math.max(current,result);
        }
        return result;
    }
}


Maximum Subarray


联系
我们