数据结构——最大子列和问题

最大子列和问题

算法一

1
T(N) = O(N^3)

算法二

1
T(N) = O(N^2)
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
#include <stdio.h>
#define N 100000

int MaxSubSeqSum2(int arr[], int n)
{
int i, j, ThisSum, MaxSum = 0;
for(i = 0; i < n; i++)
{
ThisSum = 0;
for(j = i; j < n; j++)
{
ThisSum += arr[j];
if(ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
}
}
return MaxSum;
}

int main()
{
int k, i, list[N];
scanf("%d", &k);
for(i = 0; i < k; i++)
{
scanf("%d", &list[i]);
}
printf("%d", MaxSubSeqSum2(list, k));

return 0;
}

算法三:分而治之

1
T(N) = O(NlogN)

建议尝试时间复杂度的推理过程

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
#include <stdio.h>
#define N 100000

int Max2(int x, int y)
{
return x > y ? x : y;
}

int Max3(int a, int b, int c)
{
return Max2(Max2(a, b), c);
}

int DivideAndConquer(int arr[], int left, int right)
{
if(left == right) // 递归边界
{
if(arr[left] > 0)
{
return arr[left];
}
else
{
return 0;
}
}

// 分
int MaxLeftSum, MaxRightSum, mid = (left + right) / 2;
// 递归
MaxLeftSum = DivideAndConquer(arr, left, mid);
MaxRightSum = DivideAndConquer(arr, mid + 1, right); // 注意是mid + 1

// 治
int i, LeftBorderSum = 0, RightBorderSum = 0, MaxLeftBorderSum = 0, MaxRightBorderSum = 0;
// 向左扫描
for(i = mid; i >= left; i--) // 注意是>=
{
LeftBorderSum += arr[i];
if(LeftBorderSum > MaxLeftBorderSum)
{
MaxLeftBorderSum = LeftBorderSum;
}
}
// 向右扫描
for(i = mid + 1; i <= right; i++) // 注意mid + 1 及 <=
{
RightBorderSum += arr[i];
if(RightBorderSum > MaxRightBorderSum)
{
MaxRightBorderSum = RightBorderSum;
}
}
// 返回治的结果
return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

int MaxSubSeqSum3(int arr[], int n) // 保持和前两种算法相同的函数接口
{
return DivideAndConquer(arr, 0, n - 1);
}

int main()
{
int k, i, list[N];
scanf("%d", &k);
for(i = 0; i < k; i++)
{
scanf("%d", &list[i]);
}

printf("%d", MaxSubSeqSum3(list, k));

return 0;
}

空间复杂度讨论?即
1、由于递归而产生的空间复杂度是多少?
2、算法的整体空间复杂度一共是多少?
答:
1、递归深度 = logN,每次递归所需辅助空间固定:O(1)(注意到函数调用栈以及函数传递数组参数传的是指针,每次调用不需要重新开辟空间),所以由于递归而产生的空间复杂度为O(logN)
2、数组所需辅助空间:O(N)S(N) = O(N) + O(logN),所以算法的整体空间复杂度为O(N)

算法四:在线处理

1
T(N) = O(N)
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
#include <stdio.h>
#define N 100000

int MaxSubSeqSum4(int arr[], int n)
{
int i, ThisSum = 0, MaxSum = 0;
for(i = 0; i < n; i++)
{
ThisSum += arr[i];
if(ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if(ThisSum < 0)
{
ThisSum = 0; // 关键
}
}
return MaxSum;
}

int main()
{
int k, i, list[N];
scanf("%d", &k);
for(i = 0; i < k; i++)
{
scanf("%d", &list[i]);
}

printf("%d", MaxSubSeqSum4(list, k));

return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2021 zhangguoliu
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信