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

发表于 | 阅读次数:

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

刷题平台：牛客网

连续子数组的最大和

考点：

动态规划

1、题目描述

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

2、解题思路

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

3、算法实现

C实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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");	
}

实现结果