剑指offer刷题（30）：连续子数组的最大和

雨点打透心脏的1/2处 2022-05-26 23:05 27阅读 0赞

# 剑指offer刷题（30）：连续子数组的最大和 #

刷题平台：[牛客网][Link 1]

# 连续子数组的最大和 #

## 考点： ##

动态规划

## 1、题目描述 ##

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

## 2、解题思路 ##

从第一个数字开始，往后加，如果前面的和大于0，那么我们将要继续往下累加就好；否则我们将要重新归零，然后再往下累加。在累加的时候，一旦我们求得最大值的时候我们就可以记录子数组结束的位置。

## 3、算法实现 ##

### C实现 ###

#include "stdio.h"
    
    void FindGreatestSumOfSubArray(int *a, int *length, int *start, int *end, int *sum_max);
    
    void FindGreatestSumOfSubArray(int *a, int *length, int *start, int *end, int *sum_max)
    {
        if (length <= 0)
        {
            return;
        }
        *sum_max = a[0];
        int sum_max_old = a[0];
        for (int i = 1; i < *length; i++)
        {
            if (*sum_max < 0)
            {
                *sum_max = 0;           
            }
    
            *sum_max += a[i];
            if (*sum_max < 0)
            {
                if (*sum_max > sum_max_old)
                {
                    sum_max_old = *sum_max;
                    *start = i;
                    *end = i;
                }
    
                *sum_max = 0;
                *start = i + 1;
            }
            else
            {
    
                if (*sum_max > sum_max_old)
                {
                    *end = i;
                    sum_max_old = *sum_max;
                }
            }       
        }
        if (*start > *end)
        {
            *start = *end;
        }
        *sum_max = sum_max_old;
    }
    
    int main()
    {
        int num[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4 };//−2,1,−3,4,−1,2,1,−5,4
        int length = sizeof(num) / sizeof(num[0]);
        int start = 0, end = 0, sum_max=0;
        printf("我们需要计算的数组");
        for (int i = 0; i < length; i++)
        {
            printf("%d\t",num[i]);
        }
        printf("\n");
    
        FindGreatestSumOfSubArray(num, &length, &start, &end, &sum_max);
    
        printf("\n\n");
        printf("连续子数组的最大和为：");
        printf("%d\n", sum_max);
        printf("连续子数组的最大和的起止坐标为:（%d,%d）\n", start, end);
        printf("连续子数组为：");
        for (int i = start; i <= end; i++)
        {
            if (start == end)
            {
                printf("%d\t", num[end]);
            }
            else
            {
                printf("%d\t", num[i]);
            }
        }
        printf("\n");   
    }

### 实现结果 ###

![这里写图片描述][SouthEast]

[Link 1]: https://www.nowcoder.com/ta/coding-interviews
[SouthEast]: /images/20220527/0a86d29dba93451f91de69c0d731fdde.png