求一个数组中子数组的最大和算法（Java实现）
前几天在微信订阅号“待字闺中”中看到的一篇文章《小技巧求一个数组中子数组的最大和》，提供下Java的实现，并且在对题目做下小修改，本来打算直接在微信里直接回复，但是发现无法回复，然后整理出一篇简短博客吧。
1. 原题及解答
题目：
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4,7, 2, 因此输出为该子数组的和 18。
解答：
【只有子数组“前半部分”的和为正数时，子数组的求和才有可能最大】，在这个trick条件下，只需要遍历一次数组就可以。算法是：当从头开始遍历的元素的求和为正数时，继续向后遍历。当求和为负数时，重新开始计算求和，子数组的开始重置为下一个元素。
2. Java实现
原文提供的是Python的实现，我这里通过Java来实现：
package subarraymaxsum;
public class MaxSumOfSubArray {
public int maxSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("array is null or empty.");
}
int result = array[0], mark = 0;
for (int i = 0; i < array.length; i++) {
int element = array[i];
if (mark >= 0) {
mark += element;
} else {
mark = element;
}
if (mark > result) {
result = mark;
}
}
return result;
}
public static void main(String[] args) {
MaxSumOfSubArray maxSumOfSubArray = new MaxSumOfSubArray();
int maxSum = maxSumOfSubArray.maxSum(new int[]{1, -2, 3, 10, -4, 7, 2, -5});
System.out.println(maxSum);
}
}输出： 18
其实虽然原题中指出数组里有正数和负数，当时经过实践和思考，这个算法同样适用于全是正数，或者全是负数的情况。当全为正数时，最大的和自然就是所有元素的和，当全为负数时，最大和自然就是其中最大的那个负数的值。通过此算法都能得到相应的结果。
测试代码-全是负数：
public static void main(String[] args) {
MaxSumOfSubArray maxSumOfSubArray = new MaxSumOfSubArray();
int maxSum = maxSumOfSubArray.maxSum(new int[]{-100, -3, -10, -1, -7, -2, -5});
System.out.println(maxSum);
}输出 -1
测试代码-全是正数：
public static void main(String[] args) {
MaxSumOfSubArray maxSumOfSubArray = new MaxSumOfSubArray();
int maxSum = maxSumOfSubArray.maxSum(new int[]{100, 3, 10, 1, 7, 2, 5});
System.out.println(maxSum);
}输出 128
3. 总结
该算法可以适用于任何数值数组，和数组中数组的正负无关。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
