赞
踩
对于给定的一个长度为n的整数序列,要求计算出最大的连续子数组和。以a[]={1,2,-9,5,8,2,6,-8}为例,最大和为5+8+2+6=21;
首先,是连续的子序列,再则所求和最大,那要怎样查找呢?
话不多说,一下是三种常见解法:(以函数形式呈现)
法一:一重循环
-
- int sum(int a[], int n)
- {
- int max = 0; // 最大子数组和,初始化为 0
- int b = 0; // 当前子数组和,初始化为 0
- int i, j;
-
- for(i = 0; i < n; i++) // 遍历数组 a
- {
- b += a[i]; // 将 a[i] 添加到当前子数组中
- if(b > max) // 如果当前子数组和大于最大子数组和
- max = b; // 更新最大子数组和
- else if(b < 0) // 如果当前子数组和小于 0,说明对后面的子数组和无贡献,将当前子数组和清零
- b = 0;
- }
- return max; // 返回最大子数组和
- }
-
-
对于法一:这是一个比较经典的算法,又叫 Kadane 算法。它的思路很简单,遍历整个数组,每次将当前元素加入当前子数组中,并比较当前子数组和是否超过之前的最大子数组和,如果是,就更新最大子数组和;如果当前子数组和小于 0,说明对后面的子数组和无贡献,将当前子数组和清零,重新计算后面的子数组和。
这个算法的时间复杂度为 O(n),比较高效,也比较容易理解。
法二:两重循环
- int sum(int* a, int n)
- {
- int i, j, k, max, sub = 0; // 初始化变量
-
- for(i = 0; i < n; i++) // 枚举所有可能的子数组
- {
- for(j = i; j < n; j++)
- {
- max = 0; // 初始化子数组和为 0
- for(k = i; k <= j; k++) // 计算当前子数组的和
- {
- max += a[k];
- }
- if(sub < max) // 如果当前子数组和大于之前最大子数组和
- sub = max; // 更新最大子数组和
- }
- }
- return sub; // 返回最大子数组和
- }
对于法二:这是一个暴力算法,它的思路是枚举所有可能的子数组,计算每个子数组的和,找到其中最大的。
这个算法的时间复杂度 O(n3),效率比较低,但是它的思路比较直观,也比较易于理解。如果数组规模较小,这个算法的性能表现也不错。
法三:三重循环
- int sum(int* a, int n)
- {
- int i, j; // 定义循环变量
- int max = 0, sub = 0; // 初始化最大子数组和和当前子数组和为 0
-
- for(i = 0; i < n; i++) // 枚举所有可能的子数组起始位置
- {
- sub = 0; // 将当前子数组和清零
- for(j = i; j < n; j++) // 计算当前子数组的和即可
- {
- sub += a[j];
- if(sub > max) // 如果当前子数组和大于之前最大子数组和
- max = sub; // 更新最大子数组和
- }
- }
- return max; // 返回最大子数组和
- }
对于法三:这是另一个暴力算法,它的思路是枚举所有可能的子数组起始位置和终止位置,计算每个子数组的和,找到其中最大的。
这个算法的时间复杂度为 O(n2),略低于上一个暴力算法,但效率仍然比较低。不过它的思路比较易于理解,可以帮助初学者更好地理解动态规划算法的思路。
最后,小编把主函数贴上了,需要的伙伴自取哈
- int main()
- {
- int a[]={1,2,-9,5,8,2,6,-8};
- int n=sizeof(a)/sizeof(a[0]);
- int t=sum(a,n);
- printf("%d",t);
- return 0;
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。