2018年携程实习生编程题——求子数组和的最大值

题目:给定一个数组,求出该数组的所有子数组和的最大值,要求时间复杂度为O(n)。
比如:数组[1,2,-4,5,2,-5],其中子数组[5,2]的值为7是最大的。
思路:先分两种情况:1.数组中全为负数的情况,就是找出所有负数中的最大值;2.数组中不全为负数, 遇到正数就加,当遇到负数的时候,就记录一下前面正数的和,并且改正数和再和上一个正数和做比较。同时要为乐保证事件复杂度为O(n),上面提到的两种情况要在一个数组遍历中完成,不多说了代码如下(如果有bug,小弟希望大家指出来):

        int calcuCount(int[] p)
        {
            int sum = 0;
            int b = 0;
            int num = 0;
            int tmp = p[0];
            for (int i = 0; i < p.Length; i++)
            {
                if (p[i] > 0)
                {
                    b = b + p[i];
                }
                else
                {
                    num++;
                    if (p[i] > tmp)
                    {
                        tmp = p[i];
                    }
                }

                if (b > sum)
                {
                    sum = b;
                }
            }
            if (sum == p.Length)
                sum = tmp;
            return sum;
        }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • 查看一下现有ruby source:$ gem sources 如果是ruby原来的默认source,或者之前一直...
    yehkong阅读 320评论 3 0
  • 我覺著很冷,窗外的風和頭頂的風相互吹襲著我,使我覺得很冷但同時又保存著意識。 天都黑了,很遠處的大...
    脾脾陳阅读 110评论 0 0
  • 儿子两岁多,每天早上上班是个难事。他似乎知道我早上起来就要上班离开,总是早早醒来,然后睡眼朦胧地爬到我怀里,奶声奶...
    山河万朵阅读 608评论 2 4
  • 作为一个生活在魔都将要小升初的五年级姑凉,虽然学习成绩还不错,但是不禁想说一句:你们所期望的真的是我们吗? ...
    玻璃碎片阅读 234评论 0 0