LeetCode 53. Maximum Subarray 最大連續字段和問題
考察:最大連續字段和問題。
解決問題時間復雜度:O(n)
問題隱含條件:如果給出的數集都是負數,那么最大連續字段和就是,最大的那個負數。
eg:{-2,-1} 結果應該輸出 -1 而不是 0
int maxSubArray(int* nums, int numsSize) { int maxSum = 0; //維護最大連續字段和 int currentMaxSum = 0;//當前最大和 int nextNum = 0; int singleSum = nums[0]; //存在全是負數,則singleSum 代表最大的那個 int j = 0; for (int i = 0; i < numsSize; i ++) { nextNum = nums[i]; currentMaxSum += nextNum; if (currentMaxSum > 0) { maxSum = maxSum <= currentMaxSum ? currentMaxSum: maxSum; } else { currentMaxSum = 0; j ++; singleSum = singleSum < nextNum ? nextNum : singleSum; } } maxSum = (j == numsSize) ? singleSum : maxSum; return maxSum; }
posted on 2018-09-08 23:38 ACM_Someone like you 閱讀(315) 評論(0) 收藏 舉報
浙公網安備 33010602011771號