053 最大子序和

题目

给定一个整数数组 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;      
    }
}
浙ICP备19012682号