LeetCode - 53. Maximum Subarray

題目: Maximum Subarray

給定一個整數數組 nums，找到其和最大的子數組，並返回該子數組的和。

解題思路

Kadane's Algorithm:用於求解最大子數組和的動態規劃算法。
從數組的第一個元素開始遍歷，依次計算包含當前元素的所有子數組的和，並選擇其中和最大的子數組作為當前位置的最大子數組。同時，還需要維護一個全局最大子數組和的變量，以便在遍歷過程中不斷更新最大值。
時間複雜度為 O(n)，空間複雜度為 O(1)。

Code

Java:

Runtime 2 ms(18%), Memory 73.7 MB(5.1%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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%)

1
2
3
4
5
6
7
8


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_sum

C#:

Runtime 251 ms(5.3%), Memory 49.2 MB(97.61%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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%)

1
2
3
4
5
6
7
8
9


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;
}