快乐的LeetCode --- 面试题42. 连续子数组的最大和_leetcode 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子

题目描述：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

解题思路1: 超出时间限制

最容易能想到的思路，莫过于两个for循环

代码1：

class Solution(object):
    def maxSubArray(self, nums):
        size = len(nums)
        max_num = max(nums)
        for i in range(size):
            for j in range(i+1, size+1):
                if max_num < sum(nums[i:j]):
                    max_num = sum(nums[i:j])
        return max_num
1
2
3
4
5
6
7
8
9

解题思路2: 来源于官方

代码2：

class Solution(object):
    def maxSubArray(self, nums):
        dp = []
        dp.append(nums[0])
        for i in range(1, len(nums)):
            if dp[i-1] <= 0:
                dp.append(nums[i])
            else: 
                dp.append(dp[i-1] + nums[i])  
        return max(dp)
1
2
3
4
5
6
7
8
9
10

官方代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)
1
2
3
4
5

C++解法：

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

题目来源：

https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/