求子数组的最大和-在线编程-K6K4.com

求整数数组中连续子序列之和最大值，其中整数数组可以为正数、负数、0

输入、输出描述

输入：

整数数组

输出：

连续子序列之和最大值

Example

输入：

-2,4,-2,7,-6,-1

输出：

修改

遍历整个数组，求以位置i结尾的最大连续子序列和，这里分为两种情况：

如果在位置i之前的最大连续子序列和大于0，则以位置i结尾的最大连续子序列和为位置i处的元素加上前面的连续子序列和；
如果在位置i之前的最大连续子序列和小与或等于0，则以位置i结尾的最大连续子序列和为位置i处的元素。

比较以各个i位置结尾的最大连续子序列和，即求得最大连续子序列和。

代码：

import java.util.*;

public class Main {
  public int solution(int[] input,int n) {
    int maxsum, max_before_i;
    maxsum = max_before_i = input[0];
    for (int i=1; i<n; i++) {
      if (max_before_i <= 0)
        max_before_i = input[i];
      else
        max_before_i += input[i];
      if (max_before_i > maxsum) {
        maxsum = max_before_i;  //更新最大连续子序列和
      }
    }
    return maxsum;
  }
}