题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

算法

(别的题解) $O(n)$

Talk is cheap

时间复杂度 $O(n)$

空间复杂度 $O(1)$

参考文献 无

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int tmp=nums[0],best=nums[0];
        nums.erase(nums.begin());
        for(auto v:nums){
            tmp=max(v,v+tmp);
            best=max(tmp,best);
        }
        return best;
    }
};

C 代码

int max(int a,int b){
    return a>b?a:b;
}
int maxSubArray(int* nums, int numsSize) {
    int tmp=nums[0],best=nums[0];
    for(int i=1;i<numsSize;i++){
        int v=nums[i];
        tmp=max(v,v+tmp);
        best=max(tmp,best);
    }
    return best;
}

Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        int tmp=nums[0];
        int best=nums[0];
        for(int i=1;i<nums.length;i++){
            int v=nums[i];
            tmp=Math.max(v,v+tmp);
            best=Math.max(tmp,best);
        }
        return best;
    }
}

Python 代码

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp,best=nums[0],nums[0]
        for v in nums[1:]:
            tmp=max(v,v+tmp)
            best=max(tmp,best)
        return best

Javascript 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var max=function(a,b){
    if(a>b)return a;
    return b;
};
var maxSubArray = function(nums) {
    var tmp=nums[0],best=nums[0];
    for(var i=1;i<nums.length;i++){
        var v=nums[i];
        tmp=max(v,v+tmp);
        best=max(tmp,best);
    }
    return best;
};

Python3 代码

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp,best=nums[0],nums[0]
        for v in nums[1:]:
            tmp=max(v,v+tmp)
            best=max(best,tmp)
        return best

Go 代码

func maxSubArray(nums []int) int {
    tmp,best:=nums[0],nums[0]
    for _,v:=range nums[1:]{
        tmp=max(v,v+tmp)
        best=max(best,tmp)
    }
    return best
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}