快乐的LeetCode --- 面试题42. 连续子数组的最大和

淩亂°似流年 2023-02-16 12:24 13阅读 0赞

**题目描述：**

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

--------------------

**解题思路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

--------------------

**解题思路2:** 来源于官方  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]

--------------------

**代码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)

官方代码：

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)

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

--------------------

**题目来源：**

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020061121175924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[https_leetcode-cn.com_problems_lian-xu-zi-shu-zu-de-zui-da-he-lcof]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/