LeetCode / 3 min read
LeetCode - 53. Maximum Subarray
LeetCode53
On this page
題目: Maximum Subarray
給定一個整數數組 nums，找到其和最大的子數組，並返回該子數組的和。
解題思路
Kadane's Algorithm:用於求解最大子數組和的動態規劃算法。 從數組的第一個元素開始遍歷，依次計算包含當前元素的所有子數組的和，並選擇其中和最大的子數組作為當前位置的最大子數組。同時，還需要維護一個全局最大子數組和的變量，以便在遍歷過程中不斷更新最大值。 時間複雜度為 O(n)，空間複雜度為 O(1)。
Code
Java:
Runtime 2 ms(18%), Memory 73.7 MB(5.1%)
class Solution { public int maxSubArray(int[] nums) { int current_sum = nums[0], max_sum = nums[0]; for (int i=1; i<nums.length; i++){ current_sum = Math.max(nums[i], nums[i] + current_sum); max_sum = Math.max(max_sum, current_sum); } return max_sum; }}Python3:
Runtime 808 ms(24.28%),Memory 28.6 MB(83.1%)
class Solution: def maxSubArray(self, nums: List[int]) -> int: current_sum = nums[0] max_sum = current_sum for i in range(1, len(nums)): current_sum = max(nums[i], nums[i] + current_sum) max_sum = max(max_sum, current_sum) return max_sumC#:
Runtime 251 ms(5.3%), Memory 49.2 MB(97.61%)
public class Solution { public int MaxSubArray(int[] nums) { int current_sum = nums[0]; int max_sum = current_sum; for (int i=1; i<nums.Length; i++){ current_sum = Math.Max(nums[i], nums[i] + current_sum); max_sum = Math.Max(max_sum, current_sum); } return max_sum; }}Golang:
Runtime 198 ms(5.19%), Memory 9.2 MB(56.15%)
func maxSubArray(nums []int) int { current_sum := nums[0]; max_sum := current_sum; for i:=1; i<len(nums); i++{ current_sum = max(nums[i], nums[i] + current_sum); max_sum = max(max_sum, current_sum); } return max_sum;}func max(a int, b int) int { if a > b { return a; }else{ return b; }}C++:
Runtime 122 ms(45.5%), Memory 67.8 MB(17.85%)
class Solution {public: int maxSubArray(vector<int>& nums) { int current_sum = nums[0], max_sum = nums[0]; for (int i=1; i<nums.size(); i++){ current_sum = max(nums[i], nums[i] + current_sum); max_sum = max(max_sum, current_sum); } return max_sum; }};C:
Runtime 109 ms(94.49%), Memory 12.1 MB(100%)
int maxSubArray(int* nums, int numsSize){ int current_sum = nums[0]; int max_sum = current_sum; for (int i=1; i<numsSize; i++){ current_sum = fmax(nums[i], nums[i] + current_sum); max_sum = fmax(max_sum, current_sum); } return max_sum;}