Fork me on GitHub

leetcode之53. 最大子序和

发表于 | 分类于
字数统计 499 字 | 阅读时长 2 分钟

题目描述：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
4
> 输入: [-2,1,-3,4,-1,2,1,-5,4],
> 输出: 6
> 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
>

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路：

思路一：

时间复杂度：$O(n)$, 空间复杂度：$O(n)$.

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 maxSubArray(vector<int>& nums) {
        vector<int> numss;
        numss.push_back(nums[0]);
        
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] + numss[i-1] >= nums[i])
                numss.push_back(nums[i] + numss[i-1]);
            else
                numss.push_back(nums[i]);
        }
        int count = numss[0];
        for(int j = 1;j < numss.size();j++)
        {
            count = max(count,numss[j]);
        }
        
        return count;
    }
};

升级：

求出子序和的序列,时间复杂度：$O(n)$, 空间复杂度：$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> maxSubArray_0(vector<int>& nums) {
        vector<int> numss;
        numss.push_back(nums[0]);
        // 前面代码不变
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] + numss[i-1] >= nums[i])
                numss.push_back(nums[i] + numss[i - 1]);
            else
                numss.push_back(nums[i]);
            
        }
        // 这里的代码，修改，此时需要找到最大值的下标，
        int count = numss[0];
        int index = 0;
        int high = 0;
        int j = 1;
        for(;j < numss.size();j++)
        {
            if(count < numss[j])
            {
                count = numss[j];
                index = j;
            }
        }
        int low = 0;
        high = index;
        while(index >= 0)
        {
            if(numss[index] != nums[index])
            {
                index--;
            }
            else
            {
                low = index;
                break;
            }
        }
        cout << "low is " << low << " high is " << high << endl;
        vector<int> result(nums.begin() + low,nums.begin() + high + 1); 
        return result;
    }
};

int main()
{
    vector<int> vec;
    Solution s;
    // -2,1,-3,4,-1,2,1,-5,4
    vec.push_back(-2);
    vec.push_back(1);
    vec.push_back(-3);
    vec.push_back(4);
    vec.push_back(-1);
    vec.push_back(2);
    vec.push_back(1);
    vec.push_back(-5);
    vec.push_back(4);

    vector<int> m;
    m = s.maxSubArray_0(vec);
    for(auto a : m)
    {
        cout << a << endl;
    }
    return 0;
}