用C语言实现最大子序和

用C语言实现最大子序和

1.题目描述

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

2.解题方法   贪心法

3.解题思路

从头开始遍历，找出最大子序列，可以是单个数字，也可以是一串数字。

根据贪心法的思想，可以先求局部最优子序列，通过比较，最后得到全局最优解。

以示例一为例，输入[-2, 1, -3, 4, -1, 2, 1, -5, 4]。

如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”。

4.程序代码

int maxSubArray(int* nums, int numsSize){
    int result = nums[0]; //存储最大数
    int sum = 0; //存储和最大
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        result = result > sum ? result : sum;
        if (sum < 0) sum = 0; //相当于重置最大子序起始位置，因为遇到负数一定拉低总和
    }
    return result;
}