/*! \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、求子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。