C++動態規劃計算最大子數組
例題
題目:輸入一個整形數組,數組裡有正數也有負數。數組中連續的一個或多個整數組成一個子數組,每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5,和最大的子數組為3, 10, -4, 7, 2,因此輸出為該子數組的和18。
1.求最大的子數組的和
代碼【C++】
#include <iostream> using namespace std; / // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return false / bool FindGreatestSumOfSubArray ( int *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum // the greatest sum of all sub-arrays ) { // if the input is invalid, return false if((pData == NULL) || (nLength == 0)) return false; int nCurSum = nGreatestSum = 0; for(unsigned int i = 0; i < nLength; ++i) { nCurSum += pData[i]; // if the current sum is negative, discard it if(nCurSum < 0) nCurSum = 0; // if a greater sum is found, update the greatest sum if(nCurSum > nGreatestSum) nGreatestSum = nCurSum; } // if all data are negative, find the greatest element in the array if(nGreatestSum == 0) { nGreatestSum = pData[0]; for(unsigned int i = 1; i < nLength; ++i) { if(pData[i] > nGreatestSum) nGreatestSum = pData[i]; } } return true; } int main() { int arr[] = {1, -2, 3, 10, -4, 7, 2, -5}; int iGreatestSum; FindGreatestSumOfSubArray(arr, sizeof(arr)/sizeof(int), iGreatestSum); cout << iGreatestSum << endl; return 0; }
結果
2.求和最大的相應子數組
代碼【C++】
#include <iostream> using namespace std; / // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return false / bool FindGreatestSumOfSubArray ( int *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum, // the greatest sum of all sub-arrays int &start, // Added int &end // Added ) { // if the input is invalid, return false if((pData == NULL) || (nLength == 0)) return false; int nCurSum = nGreatestSum = 0; int curStart = 0, curEnd = 0; // Added start = end = 0; // Added for(unsigned int i = 0; i < nLength; ++i) { nCurSum += pData[i]; curEnd = i; // Added // if the current sum is negative, discard it if(nCurSum < 0) { nCurSum = 0; curStart = curEnd = i + 1; // Added } // if a greater sum is found, update the greatest sum if(nCurSum > nGreatestSum) { nGreatestSum = nCurSum; start = curStart; // Added end = curEnd; // Added } } // if all data are negative, find the greatest element in the array if(nGreatestSum == 0) { nGreatestSum = pData[0]; start = end = 0; // Added for(unsigned int i = 1; i < nLength; ++i) { if(pData[i] > nGreatestSum) { nGreatestSum = pData[i]; start = end = i; // Added } } } return true; } int main() { int arr[] = {1, -2, 3, 10, -4, 7, 2, -5}; int iGreatestSum, start, end; FindGreatestSumOfSubArray(arr, sizeof(arr)/sizeof(int), iGreatestSum, start, end); cout << iGreatestSum << ": "; for(int i = start; i <= end; i++) { cout << arr[i] << " "; } return 0; }
結果
到此這篇關於C++動態規劃計算最大子數組的文章就介紹到這瞭,更多相關C++最大子數組內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C語言隊列和應用詳情
- C++實現LeetCode(154.尋找旋轉有序數組的最小值之二)
- 詳解C語言數組越界及其避免方法
- 使用C語言訪問51單片機中存儲器的核心代碼
- ECMAScript 6數組的擴展實例詳解