可视化图解算法76：最大子数组和

可视化图解算法76：最大子数组和

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 <= 105
• -104 <= nums[i] <= 104

2. 题解思路

本题求解的是最大子数组的和，要留意下，子数组是数组中的一个连续部分。我们可以通过动态规划来求解，此时可以套用动态规划的解题模板。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3.编码实现

核心代码如下：

func maxSubArray(array []int) int {
    // 1.定义状态.  i：数组arr的下标; dp[i]：数组arr[0:i]区间内的连续子数组的最大和
    dp := make([]int, len(array))
    //2.初始化边界条件：dp[0]=arr[0]
    dp[0] = array[0]
    maxValue := array[0] //题目要求：子数组最小长度为1
    //3.确定递推公式：dp[i]=max(dp[i]+arr[i],arr[i]);
    for i := 1; i < len(array); i++ {
        dp[i] = max(dp[i-1]+array[i], array[i])
        // 每次比较，保存出现的最大值
        maxValue = max(maxValue, dp[i])
    }
    //4.输出结果:dp数组中最大的元素
    fmt.Println(dp)
    return maxValue
}
​
func max(a int, b int) int {
    if a >= b {
        return a
    }
    return b
}

具体完整代码你可以参考下面视频的详细讲解。

• Python编码：B站@好易学数据结构
• Java编码：B站@好易学数据结构
• Golang编码：B站@好易学数据结构

4.总结

本题是动态规划的经典题目，如果套用我总结的动态规划模板，就很容易写出代码来，关键是要理解遍历i、dp[i]的含义。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：B站@好易学数据结构
• Java编码实现：B站@好易学数据结构
• Golang编码实现：B站@好易学数据结构

对于LeetCode数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：白日放歌须纵酒，青春作伴好还乡。