求一个数组中子数组的最大和算法(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. 总结

该算法可以适用于任何数值数组,和数组中数组的正负无关。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿凯的Excel

Python读书笔记19(函数与返回值)

为什么计算机与程序可以简化我们的工作量,因为我们只需要了解输入输出即可,不需要关心中间的计算过程。 那我们今天就聊一下如何使用函数输出返回值。 我们设想有一个函...

30660
来自专栏aCloudDeveloper

VC库中快排函数的详解

Author: bakari  Date:  2012.8.9 以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写...

22770
来自专栏Java 源码分析

优先队列

优先队列基本介绍 ​ 优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就...

29140
来自专栏机器学习从入门到成神

几种有关排序的常见面试问题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

23720
来自专栏北京马哥教育

看完这篇,你就知道Python生成器是什么

生成器是 Python 初级开发者最难理解的概念之一,虽被认为是 Python 编程中的高级技能,但在各种项目中可以随处见到生成器的身影,你得不得去理解它、使用...

389120
来自专栏猿人谷

快速排序

今天介绍快速排序,这也是在实际中最常用的一种排序算法,速度快,效率高。就像名字一样,快速排序是最优秀的一种排序算法。 思想 快速排序采用的思想是分治思想。 快速...

219100
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

32650
来自专栏大数据文摘

视觉直观感受 7 种常用排序算法

21050
来自专栏云霄雨霁

排序算法总结

13900
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

9140

扫码关注云+社区

领取腾讯云代金券