053 最大子序和.md

题目

• 题号：53
• 难度：简单
• https://leetcode-cn.com/problems/maximum-subarray/

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

示例 1:

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

示例 2:

输入: [-2,1],
输出: 1

进阶:

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

---

实现

第一种：利用暴力算法

• 状态：通过
• 202 / 202 个通过测试用例
• 执行用时: 596 ms, 在所有 C# 提交中击败了 14.18% 的用户
• 内存消耗: 24.5 MB, 在所有 C# 提交中击败了 5.88% 的用户

public class Solution {
    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        int max = int.MinValue;

        for (int i = 0; i < len; i++)
        {
            int sum = nums[i];
            if (sum > max)
            {
                max = sum;
            }
            for (int j = i + 1; j < len; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;        
    }
}

第二种：利用动态规划

动态规划的最优子结构如下：

max[i] = Max(max[i-1] + nums[i], nums[i])

• 状态：通过
• 202 / 202 个通过测试用例
• 执行用时: 136 ms, 在所有 C# 提交中击败了 91.85% 的用户
• 内存消耗: 24.4 MB, 在所有 C# 提交中击败了 5.88% 的用户

public class Solution {
    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        int[] max = new int[len];
        max[0] = nums[0];
        int result = max[0];
        for (int i = 1; i < len; i++)
        {
            if (max[i - 1] + nums[i] > nums[i])
            {
                max[i] = max[i - 1] + nums[i];
            }
            else
            {
                max[i] = nums[i];
            }
            
            if (max[i] > result)
            {
                result = max[i];
            }
        }
        return result;      
    }
}