剑指Offer3_连续子数组的最大和

题目描述：

输入一个整形数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组中和的最大值。

例如，输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出该子数组的和为18。

解题思路：

- 动态规划

定义一个数组dp，其中dp[i]表示以元素nums[i]为结尾的连续子数组的最大和，那么该连续子数组的长度也是要考虑进去的。如果dp[i-1]大于0，说明其对dp[i]产生正向影响，此时dp[i]=dp[i-1]+nums[i]。如果dp[i-1]小于等于0，说明其对dp[i]产生负向影响，此时dp[i]=nums[i]。最后要找到dp数组中的最大值即为所求。

- 贪心法

定义两个变量：maxSum表示当前的最大和，curSum表示当前的和。从头遍历数组，每遇到一个数，就把它加到当前的和中，如果当前的和变得比之前的最大和还要大，那么更新最大和。如果当前的和为负数，就舍弃掉之前的和，从当前数开始重新计算。最后返回最大和。

C++代码：