剑指Offer面试题:28.连续子数组的最大和

一、题目:连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},因此输出为该子数组的和18。

  这个题目在我去年参加校园招聘时,某公司的二面采用了机试,而题目刚好就是这道题。一般看到这道题目就会想到枚举出数组的所有子数组并求出它们的和。一个长度为n的数组,总共有n(n+1)/2个子数组。计算出所有子数组的和,最快也需要O(n2)的时间。但是最直观的方法不会是最优的解法,因此面试官不会满意这样的思路。

二、解题思路

2.1 核心步骤

Step1.从头到尾逐个累加数组中的每个数字,初始化和为0;(nCurrSum=0,nGreatestNum=int.MinValue)

Step2.首先加上第一个数字,从第二个数字开始累加,依次将累加和保存到一个临时变量(nCurrSum)中;

Step3.如果当前累加和(nCurrSum)小于0,那抛弃前面的子数组和,从下一个数字开始重新累加;相反,则将当前累加和(nCurrSum)与返回累加和(nGreatestNum)进行比较,如果nCurrSum>nGreatestNum,则更新nGreatestNum。

  这样比较进行一次遍历之后,就可以得到最终的最大累加和,时间复杂度是O(n)。下图展示了计算数组{1,-2,3,10,-4,7,2,-5}中子数组的最大和的过程:

2.2 代码实现

    /// <summary>
    /// 计算连续子数组的最大和
    /// </summary>
    public static int FindGreatestSumOfSubArray(int[] array, out bool isValidInput)
    {
        if (array == null || array.Length <= 0)
        {
            isValidInput = false;
            return 0;
        }

        isValidInput = true;

        int currSum = 0;
        int greatestSum = int.MinValue;

        for (int i = 0; i < array.Length; i++)
        {
            if(currSum <= 0)
            {
                currSum = array[i];
            }
            else
            {
                currSum += array[i];
            }

            if (currSum > greatestSum)
            {
                greatestSum = currSum;
            }
        }

        return greatestSum;
    }

三、单元测试

3.1 测试用例

    // 1, -2, 3, 10, -4, 7, 2, -5
    [TestMethod]
    public void GetGreatestNumTest1()
    {
        int[] data = { 1, -2, 3, 10, -4, 7, 2, -5 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 18);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 所有数字都是负数
    // -2, -8, -1, -5, -9
    [TestMethod]
    public void GetGreatestNumTest2()
    {
        int[] data = { -2, -8, -1, -5, -9 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, -1);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 所有数字都是正数
    // 2, 8, 1, 5, 9
    [TestMethod]
    public void GetGreatestNumTest3()
    {
        int[] data = { 2, 8, 1, 5, 9 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 25);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 无效输入
    [TestMethod]
    public void GetGreatestNumTest4()
    {
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(null, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 0);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

3.2 测试结果

  (1)测试用例通过情况

  (2)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

22720
来自专栏chenjx85的技术专栏

leetcode-78-子集(用bfs解决)

vector<vector<int>> subsets(vector<int>& nums)

54110
来自专栏计算机视觉与深度学习基础

Leetcode 218. The Skyline Problem 线段树

A city's skyline is the outer contour of the silhouette formed by all the build...

36190
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

51070
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

13410
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

39420
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

38360
来自专栏阮一峰的网络日志

Reduce 和 Transduce 的含义

学习函数式编程,必须掌握很多术语,否则根本看不懂文档。 本文介绍两个基本术语:reduce和transduce。它们非常重要,也非常有用。 ? 一、reduce...

28570
来自专栏take time, save time

你所能用到的数据结构(四)

五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

349100
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

37450

扫码关注云+社区

领取腾讯云代金券