顺序表应用7:最大子段和之分治递归法

题目简介

题目思路

  • 先考虑当前的元素是不是最后一个,如果是最后一个的话,判断该元素是不是大于0,如果大于,直接返回该函数,小于则返回0。
  • 计算中间元素左边(leftmax)的最大值和右边(rightmax)的最大值,直接用getmax()函数来进行获取
  • 找出左边suml和右边sumr的最大值,进行相加,得出一整部分元素和的最大值Max
  • 最后,将Max和leftmax、rightmax做对比,求出最大的值,return Max.
  • 不要忘了每一次进行函数的时候,cnt都要加一
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
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
int getmax(int s[], int l, int r)
{
cnt++;
if(l == r)//表示当前只剩下一个数字了,如果该数字小于0,则输出0,否则输出他的本身
{
if(s[l] < 0)
{
return 0;
}
else
{
return s[l];
}
}
int leftmax, rightmax, Max;
int mid;
mid = (l + r) / 2;//找到中间的数字
leftmax = getmax(s,l,mid);//获取到左边最大的数字
rightmax = getmax(s,mid+1,r);//获取到右边最大的数字
int suml = 0;
int sum = 0;
int sumr = 0;
for(int i = mid; i >= l; i--)//找出左边最大的数字,赋值于suml
{
sum = sum + s[i];//代表左边数字的累加
if(sum > suml)//判断是否加的是负数
{
suml = sum;
}
}
sum = 0;
for(int i = mid + 1; i <= r; i++)//找出右边最大的数字,赋值于sumr
{
sum = sum + s[i];//代表右边数字的累加
if(sum > sumr)//判断是否加的是负数
{
sumr = sum;
}
}
Max = suml + sumr;//这是一个整部分最大值
Max = max(Max,leftmax);//找寻左边最大值和整部分最大值
Max = max(Max,rightmax);//找寻右边最大值和整部分最大值
return Max;

}
int main()
{
int n;
int sum = 0;
int s[50010];
scanf("%d", &n);
for(int i = 1; i < n; i++)
{
scanf("%d", &s[i]);
}
sum = getmax(s,0,n-1);
printf("%d %d\n", sum, cnt);
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信