蓝桥杯 试题 算法提高 最大区间和(C++)

蓝桥杯 试题 算法提高 最大区间和(C++),第1张

蓝桥杯 试题 算法提高 最大区间和(C++)

最大区间和

题目浏览算法浏览核心思路

题目浏览

资源限制
时间限制:1.0s 内存限制:256.0MB

问题描述
  给定n个数A1,A2,A3……An,求两个数l,r满足l<=r并最大化Al+A(l+1)+……Ar,输出这个最大值
  
输入格式
  第一行一个数n,接下来一行有n个用空格隔开的数,第i个数表示Ai
  
输出格式
  输出仅一行,即最大区间和
  
样例输入
4
-1 -2 -3 4

样例输出
4

数据规模和约定
  每个数绝对值不超过2^30;
  n<=1000000

算法浏览
#include
#include

using namespace std;

const int N = 1000010;

int n;
long long dp[N];
long long ans = -1e9;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        long long temp;
        scanf("%lld", &temp);
        dp[i] = max(dp[i - 1] + temp, temp);
        ans = max(ans,dp[i]);
    }
    cout << ans < 
核心思路 

由于看到数据范围 n<=1000000 ,可知,这个算法一定会是一个O(n)的算法

这边可以使用动态规划来解决这个题,由于是个区间,所以可以转换为最大连续的字段和

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5718944.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存