一、题目描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/25a3767110284577a50763b860d68796.png)
二、题目解法
![在这里插入图片描述](https://img-blog.csdnimg.cn/baf76054440c4afbb678ea1e6724381d.png)
解题思路:
用 temp 记录局部最优值,用 result 记录全局最优值。
每遍历一个新元素时,判断(已遍历的连续子数组的和)加上(当前元素值),与(当前元素值)对比谁更大。
(1)如果已遍历的连续子数组的和 + 当前元素值 >= 当前元素值
说明(已遍历的连续子数组的和)是大于等于0的,令 temp = 已遍历的连续子数组的和 + 当前元素值。
(2)如果已遍历的连续子数组的和 + 当前元素值 < 当前元素值
说明(已遍历的连续子数组的和)是小于0的,加上这部分只会拖累当前元素,故应该直接抛弃掉这部分,令 * temp = 当前元素值。
(3)对比 temp 和 result,如果 temp 更大,则更新到 result 中。
核心代码
int maxSubArray(int* nums, int numsSize)
{
int temp=nums[0];
int result=nums[0];
for(int i=1;i<numsSize;i++)
{
if(temp+nums[i]>=nums[i])
{
temp+=nums[i];
}
else
{
temp=nums[i];
}
if(temp>result)
{
result=temp;
}
}
return result;
}