Leetcode053

LeetCode053：最大子序和         给定一个整数数组nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。。 ```cpp 示例:

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

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

#### 解法一：暴力法

```cpp
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
        /***********************************************************************************
        INT_MAX和INT_MIN分别表示最大、最小整数，定义在头文件limits.h中。
        因为int占4字节32位，根据二进制编码的规则，INT_MAX = 2^31-1，INT_MIN= -2^31.C/C++中，
        所有超过该限值的数，都会出现溢出，出现warning，但是并不会出现error。
        如果想表示的整数超过了该限值，可以使用长整型long long 占8字节64位。
        **************************************************************************/
        int max = INT_MIN;  
        int numsSize = int(nums.size());
        for (int i = 0; i < numsSize; i++)
        {
            int sum = 0;
            for (int j = i; j < numsSize; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }

        return max;
    }
};

解法二：贪心法

class Solution2
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
        int result = INT_MIN;
        int numsSize = int(nums.size());
        int sum = 0;
        for (int i = 0; i < numsSize; i++)
        {
            sum += nums[i];
            result = max(result, sum);
            //如果sum < 0，重新开始找子序串
            if (sum < 0)
            {
                sum = 0;
            }
        }

        return result;
    }
};

解法三：两个标记动态寻找

/**************
两个标记动态寻找
该题要找到连续子数组的最大和，可用动态寻找
即定义两个变量presum、maxsum
一个动态选择的做加法
一个记录最大值
********************/
class Solution3
{
public:
    int maxSubArray(vector<int>& nums)
    {
        if (nums.empty())
            return 0;
        int presum = nums[0];
        int maxsum = presum;
        for (int i = 1; i < int(nums.size()); i++)
        {
            presum = presum > 0 ? presum += nums[i] : nums[i];
            maxsum = max(maxsum, presum);
        }
        return maxsum;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
    vector<int> nums;
    cout << "请输入数组的大小 Size: "<<endl;
    int Size;
    cin >> Size;
    int Currval;
    cout << "请输入数组的元素: " << endl;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }

    Solution3 answer;
    cout << "最大连续子数组的和为： " << answer.maxSubArray(nums) << endl;

    system("pause");
    return 0;
}