数据结构：最大子段和问题

今天药忘吃喽~ 2022-05-31 12:51 198阅读 0赞

# 最大字段和 #

问题是这样的，在一个给定的数组中寻找子数组之和的最大值，暴力肯定是超时的，这个是个典型的动态规划DP

不过下面的做法还有点不恰当，当所有的元素都是负数的时候，这个方法就不正确， 可以在专门做一次遍历求解最大的元素，然后和dp在做比较

# 代码详解 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    const int SIZE = 6;
    int a[SIZE] = { -2,11,-4,13,-5,-2 };
    
    
    int maxSumbyDP()
    {
        int maxsum = 0;
        int dp = 0;
        int fr = 0;
        int to = 0;
        int x, y;
        for (int i = 0; i <SIZE; i++)
        {
            if (dp > 0)
            {
                dp += a[i];
                to++;
            }
            else
            {
                dp = a[i];
                fr = i;
                to = i;
            }
    
            if (dp > maxsum)
            {
                maxsum = dp;
                x = fr;
                y = to;
            }
        }
        cout << "From: " << x << " to : " << y << endl;
        cout << "MaxSum is(by DP) :" << maxsum << endl;
        return maxsum;
    }
    int main()
    {
        maxSumbyDP();
        system("pause");
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++动态规划------最大子段和的问题

目录最大子段和（动态规划C++）最大子段和的动态规划算法 4.4 最大子段和算法4.7计算最大子段和的动态规划算法算法4.8计算最大子段和的动态规划算法的

深藏阁楼爱情的钟/ 2024年03月22日 12:11/ 0 赞/ 93 阅读

相关最大子段和问题

最大子段和问题描述给定由n个整数(可能为负整数)组成的序列a1，a2， a3… ， an，寻找它的某个连续子段，使得其和最大。例如( -2,11,-4,13,

妖狐艹你老母/ 2024年03月17日 09:53/ 0 赞/ 66 阅读

相关最大子段和问题

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11

心已赠人/ 2023年10月05日 13:29/ 0 赞/ 42 阅读

相关 P1115-最大子段和

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

不念不忘少年蓝@/ 2023年06月01日 08:49/ 0 赞/ 18 阅读

相关 POJ 1050 最大子段和的延伸最大子矩阵

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。 j

野性酷女/ 2022年09月30日 03:46/ 0 赞/ 175 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 202 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 210 阅读

相关循环数组最大子段和

N个整数组成的循环序列a 1 1,a 2 2,a 3 3,…,a n n，求该序列如a i i\+a i\+1 i+1\+…+a j j的连续的子段和的最大值（循环序列是指n个

傷城~/ 2022年06月12日 12:07/ 0 赞/ 204 阅读

相关数据结构：最大子段和问题

最大字段和问题是这样的，在一个给定的数组中寻找子数组之和的最大值，暴力肯定是超时的，这个是个典型的动态规划DP 不过下面的做法还有点不恰当，当所有的元素都是负数的时候

今天药忘吃喽~/ 2022年05月31日 12:51/ 0 赞/ 199 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 254 阅读