简单算法题我重拳出击 | leetcode.[53]最大子序和-一一网

这是我参与更文挑战的第2天，活动详情查看：更文挑战

原题

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

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1
复制代码

示例 3：

输入：nums = [0]
输出：0
复制代码

示例 4：

输入：nums = [-1]
输出：-1
复制代码

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

重拳出击

并不能快速出击，这简单题怎么这么难啊，淦。

首先仔细看了看题目，关键字是连续子数组

暴力

正经人能想到是暴力解法。
一看题目，是个数组，那么就能通过循环来获得它的连续子数组(不需要拿出来所有的子数组，那样的话实在太暴力了)，写出来应该是一个双层for循环。max的初始值要足够的小，不要设置0，防止意外发生。

int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++)
{
    int sum = 0;
    for (int j = i; j < nums.length; j++)
    {
        sum = sum + nums[j];
        //因为取的是连续子数组的和，所以这里一个一个往后头加，然后找出来和最大的就行了
        if (sum > max) max = sum;
    }
}
//循环结束后max的值就是本题的答案
复制代码

^正常情况到这就结束了，但是字数不太够，没得法子^

动态规划

一看题目下面有个标签[动态规划]，发现这题居然还能用动态规划，它不写我就不知道。菜主要就是菜在这里。

然后开始套动态规划题目的板子去写：

边界条件

题目写了nums.length>=1 那这个就没什么特殊的边界了，就记一下第一个值用来推算就行。
$dp(n)=\left\{ \begin{aligned} nums[0] & &\ n = 1 \\ ??? & & \ n > 1 \\ \end{aligned} \right.$
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
后端