练习系列 - 5、求子数组的最大和

/*! \author LiuBao \date 2011/3/24 \brief 求子数组的最大和 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 思路：对长度为N的数组a从左到右扫描求和，抛弃小于0的子数组和，记函数为Sum(i)。 1、Sum(0) = a[0] 2、Sum(i) = Sum(i - 1) > 0 ? Sum(i - 1) + a[i] : a[i], (0 < i <= N - 1) Sum(i)(0 <= i <= N - 1)中最大的，Max(Sum(i)),即为最大子数组和。 */ #include <stdio.h> #include <stdlib.h>   /*! 经典递归算法，直接使用状态转移，最大值保存在*sum中 \param array 数组 \param i 递归下标i \param sum 最大值变量指针 \return Sum(i) */ int max_sum_old(const int *array, int i, int *sum) { if(i) { int last_sum = max_sum_old(array, i - 1, sum); //last_sum = Sum(i - 1)   if(last_sum > *sum) *sum = last_sum; //更新*sum使之始终等于max(Sum(i))   return last_sum > 0 ? last_sum + array[i] : array[i]; //Sum(i) = Sum(i - 1) > 0 ? Sum(i - 1) + a[i] : a[i] } else return array[0]; //Sum(0) = a[0] }   /*! 在线算法，遍历过程能够直接计算出所需的状态值，返回最大子序列和 \param array 数组 \param n 数组元素个数 \return 数组中最大子序列和 */ int max_sum(const int *array, int n) { int i; ///< 遍历下标 int sum = array[0]; ///< 最大子序列和 int current = 0; ///< 当前子序列和 int new_start = -1; ///< 新子序列开始位置 int start = -1, end = -1; ///< 最大子序列开始、结束位置   for(i = 0; i < n; ++i) { if(current > 0) // 当前子序列和 > 0 current += array[i]; // 向后扩展子序列，使之包含a[i] else // 当前子序列和 <= 0 { current = array[i]; // 抛弃前一个子序列，重新计算当前子序列 new_start = i; // 记录新子序列的开始位置 }   if(current > sum) // 若当前子序列和 > 最大子序列和 { sum = current; // 最大子序列和更新为当前子序列和 start = new_start; // 保存当前子序列的开始位置 end = i; // 保存当前子序列的结束位置 } }   printf("start: %d, end: %d\n", start, end); // 打印最大子序列开始、结束位置   return sum; }   int main() { int dataSet[] = {1, -2, 3, 10, -4, 7, 2, -19, 3, 6}; ///< 测试数据集合   /* 使用递归算法输出最大子序列和 */ int sum = 0; max_sum_old(dataSet, sizeof(dataSet) / sizeof(int), &sum); printf("Max Sum: %d\n", sum);   /* 使用在线算法输出最大子序列和 */ printf("Max Sum: %d\n", max_sum(dataSet, sizeof(dataSet) / sizeof(int)));   return 0; }

转载于:https://www.cnblogs.com/codingmylife/archive/2011/03/24/1993655.html

总结

以上是生活随笔为你收集整理的练习系列 - 5、求子数组的最大和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。