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

今天药忘吃喽~ 2022-05-31 12:51 208阅读 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 条评论，208人围观）

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

相关阅读

相关最大子段和问题

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

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

相关最大子段和问题

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

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

相关 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 赞/ 31 阅读

相关最大连续子数组和（最大子段和）

最大连续子数组和（最大子段和）一、问题描述问题：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a

桃扇骨/ 2023年06月01日 06:23/ 0 赞/ 23 阅读

相关带权的最大子段和问题

Description 在短学期和算法导论课期间，我们一共讨论了四种求解最大子段和问题的方法，上一届的期末考试也考了交替出现的子段和问题，今天我们再拓展一下，研究一下最大的

「爱情、让人受尽委屈。」/ 2023年02月23日 05:27/ 0 赞/ 13 阅读

相关最大子段和

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

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

相关最大子段和

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

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

相关循环数组最大子段和

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 赞/ 213 阅读

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

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

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

相关最大子段和

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

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