美文网首页剑指 Offer Java版剑指offer
剑指Offer Java版 面试题42:连续子数组的最大和

剑指Offer Java版 面试题42:连续子数组的最大和

作者: 孙强Jimmy | 来源:发表于2019-07-28 11:56 被阅读1次

    题目:输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

    例如,输入的数组为{1, -2, 3, 10, -4, 7, 2, -5},和最大的子数组为{3, 10, -4, 7, 2},因此输出为该子数组的和18。

    练习地址

    https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

    参考答案

    public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
            if (array == null || array.length == 0) {
                return 0;
            }
            int sum = 0, max = Integer.MIN_VALUE;
            for (int num : array) {
                if (sum <= 0) {
                    sum = num;
                } else {
                    sum += num;
                }
                if (sum > max) {
                    max = sum;
                }
            }
            return max;
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n)。
    • 空间复杂度:O(1)。

    👉剑指Offer Java版目录
    👉剑指Offer Java版专题

    相关文章

      网友评论

        本文标题:剑指Offer Java版 面试题42:连续子数组的最大和

        本文链接:https://www.haomeiwen.com/subject/xwvurctx.html