題目問的是,給一個字串,如:-1, 2, 4, -3, 5, 2, -5, 2,求連續子字串最大的和
上述例子的答案為10,因為2, 4, -3, 5, 2是總和最大的連續子字串
這題有三種解法,時間複雜度分別是O(n^3)、O(n^2)、O(n)
O(n^3)的解法很直觀,用三個for loop跑過每一個子字串:(function1)
第一個迴圈用來跑子字串的頭
第二個迴圈跑子字串的尾巴
第三個迴圈計算每一個子字串的總和
O(n^2)的解法是把三個for loop簡化為兩個,簡化的原理在於,第二個迴圈跑字串尾巴時就順便計算總和,過程中將最大的和記錄下來(best),如此便不需要第三個迴圈了。(function2)
O(n)的解法由J. B. Kadane想出,有時被稱為Kadane's algorithm,中心原理在於,index每到達一個元素的位置時,都確保擁有「以該位置為結尾的子字串」的最大和。
(若該和為負並且小於下一個元素的值,則被取代 。若為正數,則無論下一個元素的值是否大於它,都會累加。判斷的依據可以想成,加了下一個元素,和會不會變大?捨棄前面元素的和,只從下一個元素開始計算,能否獲得更大的和?)(function3)
#include <iostream> #include <algorithm> #include <limits> using namespace std; void function1(int array[]){ int best = INT_MIN; for (int i = 0; i < 8; i++) { for (int j = i; j < 8; j++) { int sum = 0; for (int k = i; k <= j; k++) { sum += array[k]; } best = max(best, sum); } } cout << best << endl; } void function2(int array[]){ int best = INT_MIN; for (int i = 0; i < 8; i++) { int sum = 0; for (int j = i; j < 8; j++) { sum += array[j]; best = max(best, sum); } } cout << best << endl; } void function3(int array[]){ int best = INT_MIN, sum = 0; for (int i = 0; i < 8; i++) { sum = max(array[i], sum + array[i]); /*以第i-1位為結尾的子字串是否要加上第i位元素,或捨棄只取第i位元素,才能獲得最大和*/ best = max(best, sum); } cout << best << endl; } int main(int argc, const char * argv[]) { int a[] = {-1, 2, 4, -3, 5, 2, -5, 2}; function1(a); function2(a); function3(a); return 0; }
沒有留言:
張貼留言