题目

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

示例:

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

思路

1.定义两个变量sum(递推和),max_sum（保存连续值的最大值）
2.如果sum<0 则sum等于重置为当前的元素 否则元素累加和
3.如果sum>max_sum 则max_sum = sum

Rust实现

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut sum = 0;
        let mut max_sum = nums[0];
        for num in nums {
            if sum < 0 {
                sum = num
            } else {
                sum += num
            }
            if sum > max_sum{
                max_sum = sum
            }
        }
        return max_sum
    }
}

GO实现

func maxSubArray(nums []int) int {
	sum := 0
	max_sum := nums[0]
	for i:=0;i < len(nums); i++ {
		if sum < 0{
			sum = nums[i]
		} else {
			sum += nums[i]
		}
		if sum > max_sum{
			max_sum = sum
		}
	}
	return max_sum
}

Python实现

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = 0
        max_sum = nums[0]
        for i in range(0,len(nums)):
            if sum < 0:
                sum = nums[i]
            else:
                sum += nums[i]
                
            if sum > max_sum:
                max_sum = sum
        return  max_sum

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let sum = 0
    let max_sum = nums[0]
    for (let i = 0;i < nums.length;i++) {
        if (sum < 0) {
            sum = nums[i]
        } else {
            sum += nums[i]
        }
        if (sum > max_sum) {
            max_sum = sum
        }
    } 
    return max_sum
};

结果

源码下载地址：

源码下载地址