力扣00053.最大子数组和

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟
最大子数组和、数组、分治、动态规划、中等

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • $1 <= nums.length <= 10^5$
  • $-10^4 <= nums[i] <= 10^4$

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
        }
        int maxSum = dp[0];
        for (int i = 1; i < n; ++i) {
            maxSum = max(maxSum, dp[i]);
        }
        return maxSum;
    }
};

结果

执行用时 : 80 ms, 击败 83.49% 使用 C++ 的用户

内存消耗 : 71.21 MB, 击败 6.83% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        }
        int maxSum = dp[0];
        for (int i = 1; i < n; ++i) {
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

结果

执行用时 : 2 ms, 击败 41.66% 使用 Java 的用户

内存消耗 : 56.18 MB, 击败 54.49% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        maxSum = max(dp)
        return maxSum

结果

执行用时 : 113 ms, 击败 45.81% 使用 Python 的用户

内存消耗 : 23.09 MB, 击败 35.87% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        maxSum = max(dp)
        return maxSum

结果

执行用时 : 125 ms, 击败 71.45% 使用 Python3 的用户

内存消耗 : 30.97 MB, 击败 57.69% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
int maxSubArray(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int maxSum = nums[0];
    int currentSum = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i];
        maxSum = (currentSum > maxSum) ? currentSum : maxSum;
    }
    return maxSum;
}

结果

执行用时 : 75 ms, 击败 98.24% 使用 C 的用户

内存消耗 : 11.72 MB, 击败 98.27% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int MaxSubArray(int[] nums) {
        int n = nums.Length;
        if (n == 0) {
            return 0;
        }
        int maxSum = nums[0];
        int currentSum = nums[0];
        for (int i = 1; i < n; ++i) {
            currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i];
            maxSum = (currentSum > maxSum) ? currentSum : maxSum;
        }
        return maxSum;
    }
}

结果

执行用时 : 247 ms, 击败 16.12% 使用 C# 的用户

内存消耗 : 60.21 MB, 击败 5.16% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @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 = (currentSum > 0) ? currentSum + nums[i] : nums[i];
        maxSum = (currentSum > maxSum) ? currentSum : maxSum;
    }
    return maxSum;
};

结果

执行用时 : 85 ms, 击败 36.15% 使用 JavaScript 的用户

内存消耗 : 57.37 MB, 击败 22.97% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxSubArray(nums: number[]): number {
    const n: number = nums.length;
    if (n === 0) {
        return 0;
    }
    let maxSum: number = nums[0];
    let currentSum: number = nums[0];
    for (let i = 1; i < n; ++i) {
        currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i];
        maxSum = (currentSum > maxSum) ? currentSum : maxSum;
    }
    return maxSum;
}

结果

执行用时 : 83 ms, 击败 66.83% 使用 TypeScript 的用户

内存消耗 : 59.46 MB, 击败 23.34% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        $maxSum = $nums[0];
        $currentSum = $nums[0];
        for ($i = 1; $i < $n; ++$i) {
            $currentSum = ($currentSum > 0) ? $currentSum + $nums[$i] : $nums[$i];
            $maxSum = ($currentSum > $maxSum) ? $currentSum : $maxSum;
        }
        return $maxSum;
    }
}

结果

执行用时 : 186 ms, 击败 92.16% 使用 PHP 的用户

内存消耗 : 27.15 MB, 击败 80.39% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        let n = nums.count
        if n == 0 {
            return 0
        }
        var maxSum = nums[0]
        var currentSum = nums[0]
        for i in 1..<n {
            currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i]
            maxSum = max(currentSum, maxSum)
        }
        return maxSum
    }
}

结果

执行用时 : 304 ms, 击败 89.96% 使用 Swift 的用户

内存消耗 : 19.52 MB, 击败 40.17% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    fun maxSubArray(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) {
            return 0
        }
        var maxSum = nums[0]
        var currentSum = nums[0]
        for (i in 1 until n) {
            currentSum = if (currentSum > 0) currentSum + nums[i] else nums[i]
            maxSum = maxOf(currentSum, maxSum)
        }
        return maxSum
    }
}

结果

执行用时 : 478 ms, 击败 27.67% 使用 Kotlin 的用户

内存消耗 : 58.28 MB, 击败 18.87% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  int maxSubArray(List<int> nums) {
    int n = nums.length;
    if (n == 0) {
      return 0;
    }
    int maxSum = nums[0];
    int currentSum = nums[0];
    for (int i = 1; i < n; ++i) {
      currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i];
      maxSum = (currentSum > maxSum) ? currentSum : maxSum;
    }
    return maxSum;
  }
}

结果

执行用时 : 368 ms, 击败 42.86% 使用 Dart 的用户

内存消耗 : 175.44 MB, 击败 92.86% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSubArray(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    maxSum := nums[0]
    currentSum := nums[0]
    for i := 1; i < n; i++ {
        if currentSum > 0 {
            currentSum += nums[i]
        } else {
            currentSum = nums[i]
        }
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

结果

执行用时 : 79 ms, 击败 83.53% 使用 Go 的用户

内存消耗 : 7.84 MB, 击败 82.57% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
    n = nums.length
    return 0 if n == 0
    max_sum = nums[0]
    current_sum = nums[0]
    (1...n).each do |i|
        current_sum = current_sum > 0 ? current_sum + nums[i] : nums[i]
        max_sum = [max_sum, current_sum].max
    end
    max_sum
end

结果

执行用时 : 120 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 214.20 MB, 击败 13.33% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
object Solution {
  def maxSubArray(nums: Array[Int]): Int = {
    val n = nums.length
    if (n == 0) {
      return 0
    }
    var maxSum = nums(0)
    var currentSum = nums(0)
    for (i <- 1 until n) {
      currentSum = if (currentSum > 0) currentSum + nums(i) else nums(i)
      maxSum = math.max(maxSum, currentSum)
    }
    maxSum
  }
}

结果

执行用时 : 828 ms, 击败 30.77% 使用 Scala 的用户

内存消耗 : 74.23 MB, 击败 46.15% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 0 {
            return 0;
        }
        let mut max_sum = nums[0];
        let mut current_sum = nums[0];
        for i in 1..n {
            current_sum = if current_sum > 0 {
                current_sum + nums[i]
            } else {
                nums[i]
            };
            max_sum = max_sum.max(current_sum);
        }
        max_sum
    }
}

结果

执行用时 : 9 ms, 击败 64.43% 使用 Rust 的用户

内存消耗 : 3.03 MB, 击败 98.04% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户