题目：https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

我的方法一：动态规划

步骤

1. 转移方程
   dp[n]表示以第n为数字为结尾的连续子串的最大和。所以n的取值从0到nums.size()-1
   dp[n] = dp[n-1]<0?nums[n]:dp[n-1]+nums[n]
2. 边界条件
   2.1 nums的长度要大于1
3. 计算顺序
   初始dp[0] = nums[0]
   dp[1] dp[2] dp[n]

class Solution {
public:
    //dp[n]表示包含最后一位数字的连续数组的最大值
    //dp[n] = dp[n-1]<=0?nums[n]:dp[n-1]+nums[n]
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0];
        int max = nums[0];
        int nums_size = nums.size();

        for(int i = 1; i<nums_size;i++){
            if(dp<0){
                dp = nums[i];
            }else{
                dp += nums[i];
            }

            if(max<dp){
                max = dp;
            }
        }

        return max;
    }
};

其他更好的算法

贪心算法

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/