Please enable Javascript to view the contents

剑指office（二十八）数组中出现次数超过一半的数字

 ·  ☕ 1 分钟  ·  🎅 YSL

题目描述

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

示例1

输入

[1,-2,3,10,-4,7,2,-5]

返回值

18

方法一:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
            return 0;
        int maxsum = array[0];
        int sum = 0;
        for(int i=0;i<array.size();i++)
        {
            if(sum<0)
            {
                sum = array[i];
            }else
            {
                sum += array[i];
            }
            if(sum>maxsum)
                maxsum = sum;
        }
        return maxsum;
    }
};

方法二:

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
            return 0;
        int sum = array[0];
        int lastSum = 0;
        int ret = sum;
        for(int i=0;i<array.size();i++)
        {
            sum = max(array[i],lastSum+array[i]);
            lastSum = sum;
            ret = max(sum,ret);
        }
        return ret;
    }
};

相关内容