求解最大连续子序列和的几种方法（C语言版）

您所在的位置：网站首页 › 最大子序列和问题c语言 › 求解最大连续子序列和的几种方法（C语言版）

求解最大连续子序列和的几种方法（C语言版）

#求解最大连续子序列和的几种方法（C语言版）| 来源: 网络整理| 查看: 265

求解最大连续子序列和，即以下问题

给定一个整数数组arr及其长度arrSize，试找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。示例：int maxSubSum_BF(int *arr, int arrSize) ①输入[4,-3,5,-2]，输出6 ②输入[-1,2,-6,3]，输出3 ③输入[4,-3,5,-2,-1,2,6,-2]，输出11

下面我们将采取不同方法，从不同角度解决这个问题

穷举法

首先自然是暴力的穷举法了。

int maxSubArray(int* nums, int numsSize){ int sum = 0; int max = nums[0]; for(int i=0;i for(int k=i;ksum?max:sum; } } return max; }//时间复杂度O(n^3)

测试一下，没有问题。通过用例提交一下，没有……？超时了。超出时间限制难道就不能用穷举法了吗？我不甘心，再优化一下。

int maxSubArray(int* nums, int numsSize){ int sum = 0; int max = nums[0]; for(int i=0;i sum += nums[j]; max = max>sum?max:sum; } } return max; }//时间复杂度O(n^2)

依然是穷举，但减少了重复计算，时间复杂度从n3让降低到了n2，我们拭目以待。在这里插入图片描述仍有一个用例未通过……失败。看来穷举法这条路是走不通了，让我们试试其他方法。

贪心法

只要连续子序列的和为正，那么它就有可能连接上后面的数，成为最大子序列和。但如果一个连续子序列的和为负，那它就没有价值，可以彻底放弃。

于是，我们用贪心法：

int maxSubArray(int *arr, int arrSize) { int count = 0, maxSum = INT32_MIN; for (int i = 0; i int *dp, maxSum = arr[0]; dp = malloc(sizeof(int)*arrSize); //创建表 dp[0] = arr[0]; //初始化表 for (int i = 1; i

【本文地址】

求解最大连续子序列和的几种方法（C语言版）

求解最大连续子序列和的几种方法（C语言版）

今日新闻

推荐新闻