算法导论-分而治之-最大子数组(含动态规划解法)

这篇具有很好参考价值的文章主要介绍了算法导论-分而治之-最大子数组(含动态规划解法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法导论-分而治之篇

最大子数组问题

分治法
把一个问题分成(同类的)几个子问题。
递归地解决(征服)每个子问题。
将子问题的解决方案组合成整体解决方案。

通常的使用
将大小为n的问题分成两个大小为n / 2的子问题。
递归求解(攻克)两个子问题。
将两个方案组合成整体方案。

当子问题足够大以进行递归求解时,称其为递归情况(recursive case)
一旦子问题变得很小,以至不再需要递归的程度,就说递归“结束(bottom out)”了,已经回到了基本情况(base case)

最大子数组(Max Subarray)问题,是计算机科学与技术领域中一种常见的算法问题,主要可以利用分治思想进行快速实现。

最大子数组问题描述如下:假如我们有一个数组,数组中的元素有正数和负数,如何在数组中找到一段连续的子数组,使得子数组各个元素之和最大。

1 分治法求解最大子数组问题

在最大子数组问题之后,我们一起来看一下如何利用分治思想求解最大子数组问题。这里我们假设待初始的数组为 [12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10],记为数组 A,并用 A [low,high] 表示这个数组,其中 low,high 是这个数组的最小最大下标, low = 0,high = A.length -1 , 然后我们需要找到该数组的其中某一个最大子数组。

Tips: 这里我们需要注意,同一数组的最大子数组可能有多个,所以我们在这里求解的时候只说求解某一个最大子数组。

1.1 分治算法求解思路

本部分完全参考自这篇文章
https://blog.csdn.net/mukewangguanfang/article/details/128828639
在这里,我们用分治算法求解最大子数组问题,主要思路如下:

步骤 1:
找到数组 A 的中间元素,其下标记为 mid,根据分治策略,将数组 A [low,high] 根据中间元素划分为 A [low,mid], A [mid+1,high] 两个部分;

步骤 2:
假设数组 A 的最大子数组为 A [i, j],那么 A [i, j] 只有以下三种可能:
a: 最大子数组 A [i, j] 完全位于 A [low, mid] 中,此时有 low <= i <= j <= mid;
b: 最大子数组 A [i, j] 完全位于 A [mid+1, high] 中,此时有 mid+1 <= i <= j <= high;
c: 最大子数组 A [i, j] 跨域了中间元素,则 low <= i <= mid <= j <= high。
分别计算上述三种对应的最大子数组的结果;
Tips: 在这里,情况 a 和情况 b 这两种情况所得的子问题和之前求解数组 A 的最大子数组的问题形式完全一样,这里是分治思想的主要体现,将大的问题拆分成了两个相同形式的小问题;情况 c 这时候可以直接求解,在 3.2 节中会具体介绍其求解过程。

步骤 3
对步骤 2 三种情况的求解结果进行比较,其中最大子数组的结果为最大值的情况就是我们的所求结果。

1.2 代码实现
#include <iostream>
#include <cmath>
using namespace std;

// 这个跨越中线的解一定是[l,mid]与[mid+1, r]组成
int findMaxCrossSubarray(int arr[], int l, int r)
{
    if (l == r)
        return arr[l];
    else
    {
        int m = (l + r) / 2;
        int left = m, right = m + 1;
        int maxLeftSum = arr[m], maxRightSum = arr[m + 1];
        int leftSum = 0, rightSum = 0;
        for (int i = m; i >= l; i--)
        {
            leftSum += arr[i];
            if (maxLeftSum < leftSum)
            {
                maxLeftSum = leftSum;
                left = i;
            }
        }

        for (int i = m + 1; i <= r; i++)
        {
            rightSum += arr[i];
            if (maxRightSum < rightSum)
            {
                maxRightSum = rightSum;
                right = i;
            }
        }
        return maxLeftSum + maxRightSum;
    }
}
int findMaxSubarray(int arr[], int l, int r)
{
    if (l == r)
        return arr[l];
    else
    {
        int m = (l + r) / 2;
        int left = findMaxSubarray(arr, l, m);
        int right = findMaxSubarray(arr, m + 1, r);
        int mid = findMaxCrossSubarray(arr, l, r);
        //选择最大的数输出
        if (mid >= right && mid >= left)
            return mid;
        else if (right >= mid && right >= left)
            return right;
        else
            return left;
    }
}
int main()
{
    int arr[] = {5, 4, -1, 7, 8};
    cout << findMaxSubarray(arr, 0, 4);
    return 0;
}
//测试数据来着
https://leetcode.cn/problems/maximum-subarray/

2 动态规划法解决最大子数组问题

此部分参考此文章
https://blog.csdn.net/qq_36445477/article/details/105394002

1)分析问题结构: dp的第一步为分析问题结构,找到该问题的最佳子结构性质:对n个元素的数组arr[n]求解最大子数组和maxSum(n), 首先去找 maxSum(n) 和 maxSum(n-1) 的关系。

假设我们已经知道前n-1个元素的最大子数组和 maxSum(n-1), 设前n个元素中以第n元素结尾的最大子数组和为 P(n) , 则

maxSum(n) = max{ maxSum(n-1), P(n) }

继续观察 P(n) 和 P(n-1) 的关系: 若以第n-1个元素结尾的最大子数组和 P(n-1) 加上第n个元素的和大于第n个元素(即P(n-1)>0),那么以第n个元素结尾的最大子数组和为 P(n) = P(n-1) + arr[n],否则 P(n) 就等于arrr[n] 第n个元素本身, 即:

P(n) = max{ P(n-1)+arr[n], arr[n] }

我们已经找到了maxSum(n)和maxSum(n-1)子问题的关系,这就是最大子数组和问题的最优子结构性质。

2)构造递推式: 我们通过分析最优子结构性质。已经得到了dp的递推式:

P(n) = max{ P(n-1)+arr[n], arr[n] }
maxSum(n) = max{ maxSum(n-1), P(n) }

3)初始化数组,自底向上求解: 构造两个一维数组 maxSum 和 P ; P[i]: 数组前i的元素中包含元素i的最大子数组和; maxSum[i]: 数组前i个元素中的最大子数组和。

设没有元素的数组最大子数组和为负无穷以便于求解,即初始化P[0] 和maxSum[0] 为负无穷,而后以 i := 1 to n,自底向上求解,得到 **maxSum[n]**的值即为最大子数组和

代码部分如下文章来源地址https://www.toymoban.com/news/detail-770236.html

#include <iostream>
using namespace std;
int DPgetMaxSubarray(int arr[], int l, int r)
{
    // 获得前n个元素以第n元素结尾的最大子数组和为 P(n)
    int p[20];
    int maxSum[20];
    p[0] = arr[0];
    maxSum[0] = arr[0];
    for (int i = 1; i < r - l + 1; i++)
    {
        if (p[i - 1] + arr[i] > arr[i])
            p[i] = p[i - 1] + arr[i];
        else
            p[i] = arr[i];
    }
    for (int i = 1; i <= r - l; i++)
    {
        if (maxSum[i - 1] > p[i])
            maxSum[i] = maxSum[i - 1];
        else
            maxSum[i] = p[i];
    }
    return maxSum[r];
}

int main()
{
    int arr[] = {5, 4, -1, 7, 8};
    cout << DPgetMaxSubarray(arr, 0, 4);
    return 0;
}

到了这里,关于算法导论-分而治之-最大子数组(含动态规划解法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • dp算法 力扣152乘积最大子数组

    本文是Java代码!! 152. 乘积最大子数组 - 力扣(LeetCode) 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入

    2024年02月13日
    浏览(40)
  • 算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

    Hello,大家好,我是星恒 呜呜呜,今天给大家带来的又是一道经典的动归难题。 题目:leetcode 410 给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k_ 个非空的连续子数组。 设计一个算法使得这 k _个子数组各自和的最大值最小。 示例: 示例 1: 示例 2: 示例

    2024年01月22日
    浏览(46)
  • 算法:数组中的最大差值---“打擂台法“

    文章来源: https://blog.csdn.net/weixin_45630258/article/details/132737088 欢迎各位大佬指点、三连 1、题目: 给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。 2、 分析特点: 求最大差值 == 最大值 - 最小值 只需要遍历价格数组一

    2024年02月09日
    浏览(42)
  • 贪心算法求数组中能组成三角形的最大周长

    题目:三角形的最大周长 给定由一些正数(代表长度)组成的数组arr,返回由其中三个长度组成的、面积不为零的三角形的最大周长。 如果不能形成任何面积不为零的三角形,返回`0。 分析: 对数组排序,再从大到小选择三个数, 再判断是否能构成三角形,可以直接返回三数之

    2024年02月12日
    浏览(46)
  • 算法leetcode|53. 最大子数组和(rust重拳出击)

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 1 = nums.length = 10 5 -10 4 = nums[i] = 10 4 面对这道算法题目,二当家的再次陷入了沉思。 刚开始以为要暴力破解,双循环什么的,但

    2024年02月08日
    浏览(41)
  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(99)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(43)
  • 归并算法:分治而治的高效算法大揭秘(图文详解)

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 : 《数据结构算法》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 归并算法是我们算法中最常见的算法之一,其思想非常巧妙。本身归并是只能归并有序数组但是当我们利用了二路归并分治法之后,就可以使用归并的思想来帮我

    2024年02月03日
    浏览(45)
  • 算法 贪心1 || 455.分发饼干 376. 摆动序列 53. 最大子数组和

    什么是贪心:贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 但是贪心没有套路,做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。 很容易想到,把孩子的胃口和饼干大小都排序,都从最小值开始遍历。如果最小的饼干无法满足最

    2023年04月16日
    浏览(47)
  • 算法习题之子数组达到规定累加和的最大长度系列问题

    题目一主要技巧:利用单调性优化 题目二主要技巧:利用预处理结构优化 + 讨论开头结尾 题目三主要技巧:假设答案法+淘汰可能性

    2024年02月12日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包