#LeetCode:53. Maximum Subarray

從頭開始加,當總和比加的該項還小的時候就換成該項的值,一直到最後將加過的值裡面最大的記住即是答案。

C++(8ms)

/*******************************************************/
/* LeetCode 53. Maximum Subarray                       */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/16                                 */
/*******************************************************/
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    for(int i = 1 ; i < nums.size() ; ++i){
      currentSum = max(currentSum + nums[i], nums[i]);
      maxSum = max(currentSum, maxSum);
    }

    return maxSum;
  }
};

回應

目前無留言,歡迎留言!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: