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.

描述

给出一个整型数组，求连续子串的最大和

分析

假设前 k 个整数中，A[i] 到 A[k] 的子串和最大，为 sum(i,k)，取下一个元素 A[k+1]，有以下三种情况：

  • sum(i,k+1) < 0，代表会给之后的子串带来负影响，所以使子串从下一个元素开始重新累加
  • sum(i,k+1) > 0，代表会给之后的子串带来正影响，所以继续累加
  • sum(i,k+1) == 0，代表并不会影响之后的子串，所以是否累加并不影响，和 sum(i,k+1) > 0 一起处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int maxSubArray(int[] A) {

        int n = A.length;
        int max, sum;
        max = sum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {

            if (sum < 0) {
                sum = A[i];
            } else {
                sum += A[i];
            }

            if (sum > max) {
                max = sum;
            }
        }

        return max;
    }
}