LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 遍历每个数，计算以当前数为子数组尾元素时的最大和。当上次的和为负数时，则从当前数开始重新计算和

class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int res = INT_MIN;
    int sum = 0;
    for (auto& x : nums) {
      if (sum >= 0) {
        sum += x;
      } else {
        sum = x;
      }
      res = max(res, sum);
    }
    return res;
  }
};

• 动态规划，dp[i] 表示以 nums[i] 为子数组尾元素时的最大和

class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    if (empty(nums)) {
      return 0;
    }
    vector<int> dp(size(nums));
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < size(dp); ++i) {
      dp[i] = max(nums[i], dp[i - 1] + nums[i]);
      res = max(res, dp[i]);
    }
    return res;
  }
};