53.最大子数组和

LeetCode LeetCode 数组分治动态规划

发布时间 : 2000-01-10 00:05

字数:2.1k 阅读 :

评论:

53.最大子数组和

53.最大子数组和

53.1 题目

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

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

53.2 题解

动态规划

// 方法一：动态规划
// preMax 表示以当前位置为结尾的子数组的最大和
// 更新 preMax 的规则是选择当前元素 num 或者将当前元素加上前一个位置的最大和 preMax + num，取两者中较大的值。
// 这样做的目的是保证 preMax 始终表示以当前位置结尾的最大子数组和
// 因为preMax代表着当前元素前的子数组的最大和
// 在遍历过程中，不断比较并更新整个过程中的最大子数组和 result。
// 如果当前位置的 preMax 大于 result，则更新 result。
static int MaxSubArray1(int[] nums)
{
    // 初始化前一个位置的最大和为0
    int preMax = 0;

    // 初始最大子数组和为数组的第一个元素
    int result = nums[0];

    // 遍历数组中的每个元素
    foreach (int nowNum in nums)
    {
        // 更新当前位置的最大和，选择当前元素或者当前元素加上前一个位置的最大和
        preMax = Math.Max(preMax + nowNum, nowNum);

        // 更新整个过程中的最大子数组和
        result = Math.Max(result, preMax);
    }

    // 返回最终的最大子数组和
    return result;
}

分治法

// 方法二：分治法
// 递归传入起始终止位置，中间砍一半，得到左右子数组的最大子数组和，把这两个最大子数组和和跨越重点融合后最大子数组和进行比较返回最大值
static int MaxSubArray2(int[] nums)
{
    // 调用分治法辅助函数，传入数组和数组的起始和结束位置
    return MaxSubArray2Helper(nums, 0, nums.Length - 1);
}

// 分治法辅助函数，用于求解最大子数组和
static int MaxSubArray2Helper(int[] nums, int left, int right)
{
    // 当起始位置等于结束位置时，说明数组中只有一个元素，直接返回该元素
    if (left == right)
        return nums[left];

    // 计算数组的中间位置
    int mid = (left + right) / 2;

    // 递归调用分治法，分别求解左右两部分的最大子数组和
    int leftMax = MaxSubArray2Helper(nums, left, mid);
    int rightMax = MaxSubArray2Helper(nums, mid + 1, right);

    // 计算跨越中点的最大子数组和
    int crossMax = MaxCrossingSubArray(nums, left, mid, right);

    // 返回左、右、和跨越中点的三者中的最大值作为最终结果
    return Math.Max(Math.Max(leftMax, rightMax), crossMax);
}

// 计算跨越中点的最大子数组和
static int MaxCrossingSubArray(int[] nums, int left, int mid, int right)
{
    // 初始化左半部分的最大和为负无穷
    int leftSum = int.MinValue;
    // 用于累加左半部分的和
    int tempLeftSum = 0;

    // 从中点向左遍历，找出左半部分的最大和
    for (int i = mid; i >= left; i--)
    {
        tempLeftSum += nums[i];
        // 更新左半部分的最大和
        leftSum = Math.Max(leftSum, tempLeftSum);
    }

    // 初始化右半部分的最大和为负无穷
    int rightSum = int.MinValue;
    // 用于累加右半部分的和
    int tempRightSum = 0;

    // 从中点向右遍历，找出右半部分的最大和
    for (int i = mid + 1; i <= right; i++)
    {
        tempRightSum += nums[i];
        // 更新右半部分的最大和
        rightSum = Math.Max(rightSum, tempRightSum);
    }

    // 返回左半部分和右半部分的最大和之和，即跨越中点的最大子数组和
    return leftSum + rightSum;
}

53.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组
        //（子数组最少包含一个元素），返回其最大和。
        // 子数组 是数组中的一个连续部分。

        // 示例 1：
        // 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
        // 输出：6
        // 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

        // 示例 2：
        // 输入：nums = [1]
        // 输出：1

        // 示例 3：
        // 输入：nums = [5,4,-1,7,8]
        // 输出：23

        // 提示：
        // 1 <= nums.length <= 105
        // -104 <= nums[i] <= 104

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

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int result1 = MaxSubArray1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = MaxSubArray2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 1 };
        int result2 = MaxSubArray1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = MaxSubArray2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int[] nums3 = { 5, 4, -1, 7, 8 };
        int result3 = MaxSubArray1(nums3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        int result3_2 = MaxSubArray2(nums3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：动态规划
    // preMax 表示以当前位置为结尾的子数组的最大和
    // 更新 preMax 的规则是选择当前元素 num 或者将当前元素加上前一个位置的最大和 preMax + num，取两者中较大的值。
    // 这样做的目的是保证 preMax 始终表示以当前位置结尾的最大子数组和
    // 因为preMax代表着当前元素前的子数组的最大和
    // 在遍历过程中，不断比较并更新整个过程中的最大子数组和 result。
    // 如果当前位置的 preMax 大于 result，则更新 result。
    static int MaxSubArray1(int[] nums)
    {
        // 初始化前一个位置的最大和为0
        int preMax = 0;

        // 初始最大子数组和为数组的第一个元素
        int result = nums[0];

        // 遍历数组中的每个元素
        foreach (int nowNum in nums)
        {
            // 更新当前位置的最大和，选择当前元素或者当前元素加上前一个位置的最大和
            preMax = Math.Max(preMax + nowNum, nowNum);

            // 更新整个过程中的最大子数组和
            result = Math.Max(result, preMax);
        }

        // 返回最终的最大子数组和
        return result;
    }

    // 方法二：分治法
    // 递归传入起始终止位置，中间砍一半，得到左右子数组的最大子数组和，把这两个最大子数组和和跨越重点融合后最大子数组和进行比较返回最大值
    static int MaxSubArray2(int[] nums)
    {
        // 调用分治法辅助函数，传入数组和数组的起始和结束位置
        return MaxSubArray2Helper(nums, 0, nums.Length - 1);
    }

    // 分治法辅助函数，用于求解最大子数组和
    static int MaxSubArray2Helper(int[] nums, int left, int right)
    {
        // 当起始位置等于结束位置时，说明数组中只有一个元素，直接返回该元素
        if (left == right)
            return nums[left];

        // 计算数组的中间位置
        int mid = (left + right) / 2;

        // 递归调用分治法，分别求解左右两部分的最大子数组和
        int leftMax = MaxSubArray2Helper(nums, left, mid);
        int rightMax = MaxSubArray2Helper(nums, mid + 1, right);

        // 计算跨越中点的最大子数组和
        int crossMax = MaxCrossingSubArray(nums, left, mid, right);

        // 返回左、右、和跨越中点的三者中的最大值作为最终结果
        return Math.Max(Math.Max(leftMax, rightMax), crossMax);
    }

    // 计算跨越中点的最大子数组和
    static int MaxCrossingSubArray(int[] nums, int left, int mid, int right)
    {
        // 初始化左半部分的最大和为负无穷
        int leftSum = int.MinValue;
        // 用于累加左半部分的和
        int tempLeftSum = 0;

        // 从中点向左遍历，找出左半部分的最大和
        for (int i = mid; i >= left; i--)
        {
            tempLeftSum += nums[i];
            // 更新左半部分的最大和
            leftSum = Math.Max(leftSum, tempLeftSum);
        }

        // 初始化右半部分的最大和为负无穷
        int rightSum = int.MinValue;
        // 用于累加右半部分的和
        int tempRightSum = 0;

        // 从中点向右遍历，找出右半部分的最大和
        for (int i = mid + 1; i <= right; i++)
        {
            tempRightSum += nums[i];
            // 更新右半部分的最大和
            rightSum = Math.Max(rightSum, tempRightSum);
        }

        // 返回左半部分和右半部分的最大和之和，即跨越中点的最大子数组和
        return leftSum + rightSum;
    }

    #endregion
}

53.4 运行结果

示例1 方法1 输出：6
示例1 方法2 输出：6
示例2 方法1 输出：1
示例2 方法2 输出：1
示例3 方法1 输出：23
示例3 方法2 输出：23

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com