53. Maximum Subarray
給定一個整數數組 nums，找到和最大的子數組，並返回其和。
範例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4] 輸出：6 解釋：子數組 [4,-1,2,1] 的和最大，為 6。
Python
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
31.05MB, 540ms
C++
#include <vector>
#include <algorithm> // For std::max
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum = nums[0];
int current_sum = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
current_sum = max(nums[i], current_sum + nums[i]);
max_sum = max(max_sum, current_sum);
}
return max_sum;
}
};
70.26MB, 71ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
if (nums.length === 0) {
return 0;
}
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
};
57.14MB, 78ms
