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.

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.

很自然的可以想到方法，暴力枚举,复杂度O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int maxSubArray(int[] nums) {
        int ans=Integer.MIN_VALUE;
        int len=nums.length;
        for(int i=0;i<len;i++)
        {
            for(int j=i;j<len;j++)
            {
                int sum=0;
                for(int k=i;k<=j;k++)
                {
                    sum+=nums[k];
                    if(sum>ans)
                    {
                        ans=sum;
                    }
                }
            }
        }
        return ans;
    }
}

如何对上述算法进行改进呢？这就要看哪儿重复计算了
我们发现在计算sum的时候，没个区间都是单独计算一遍，这里重复了，所以改进如下,复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int maxSubArray(int[] nums) {
        int ans=Integer.MIN_VALUE;
        int len=nums.length;
        for(int i=0;i<len;i++)
        {
            int sum=0;
            for(int j=i;j<len;j++)
            {
                sum+=nums[j];
                if(sum>ans)
                {
                    ans=sum;
                }
            }
        }
        return ans;
    }
}

还可以改进，用贪心的思想
每计算一个sum，比较是否比ans大，相当于记录了最大的sum。
如果sum是正数，如果继续加正数，sum肯定在增长
如果加了一个负数，其实无所谓，因为之前比较大的sum已经被记录了。
如果sum变成了一个负数，则重置sum=0，因为加个负数计算，肯定不会是最大的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int maxSubArray(int[] nums) {
        int ans=Integer.MIN_VALUE;
        int sum=0;
        for(int i=0;i<nums.length;i++)
        {
            sum+=nums[i];
            if(sum>ans)
                ans=sum;
            if(sum<0)
                sum=0;
        }
        return ans;
    }
}