当前位置: 首页 > news >正文

洛谷 P1115 最大子段和

题目链接:P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数,表示序列的长度 n。

第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 ai。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 [3, 5] 子段 {3, -1, 2},其和为 4。

数据规模与约定

  • 对于 40% 的数据,保证 n ≤ 2 × 10^3。
  • 对于 100% 的数据,保证 1 ≤ n ≤ 2 × 10^5,−10^4 ≤ ai ≤ 10^4。

AC code 1:(动态规划,线性dp)——使用dp数组存放每一个状态

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;int main()
{int n;cin>>n;vector<int> a(n);for(int i = 0 ; i < n ; i ++)cin>>a[i];vector<int> dp(n); // dp[i] 表示以下标 i 结尾的最大字段和dp[0] = a[0];int res = dp[0];for(int i = 1 ; i < n ; i ++){dp[i] = max(dp[i - 1] + a[i] , a[i]);res = max(res , dp[i]);}cout<<res;return 0;
} 

AC code 2: (发现每次只需要使用上一个状态(dp[i - 1]),因此可以直接使用一个变量保存上一个状态即可,减少额外的空间开销)

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;int main()
{int n;cin>>n;vector<int> a(n);for(int i = 0 ; i < n ; i ++)cin>>a[i];int temp = a[0];int res = temp;for(int i = 1 ; i < n ; i ++){temp = max(temp + a[i] , a[i]);res = max(res , temp);}cout<<res;return 0;
} 

当然,这题也可以使用更为精妙的“分治”思想求解。

http://www.lryc.cn/news/32607.html

相关文章:

  • 【Linux】-- 权限和Shell运行原理
  • C++各类设计模式及实现详解
  • 【Linux】进程理解与学习(Ⅰ)
  • 认识代码之前,请先认识你自己 |《编程人生》
  • react学习笔记-5:react路由
  • [Python图像处理] 使用高通滤波器实现同态滤波
  • PyTorch深度学习:60分钟入门
  • C语言指针常见问题汇总
  • Coremail邮件系统全新上线存档邮箱功能
  • Python绘图
  • 【独家】华为OD机试 - 第K个最小码值的字母(C 语言解题)
  • 整数反转(python)
  • 【数据结构】二叉树与堆
  • Git图解-常用命令操作-可视化
  • C语言-基础了解-20-typedef
  • Ubuntu系统升级16.04升级18.04
  • CM6.3.2启用Kerberos(附问题解决)
  • QML 动画(组合动画)
  • 【PHP代码注入】PHP代码注入漏洞
  • Python 常用语句同C/C++、Java的不同
  • 一把火烧掉了苹果摆脱中国制造的幻想,印度制造难担重任
  • 常用的 JavaScript 数组 API
  • 海思3531a pjsip交叉编译
  • 《安富莱嵌入式周报》第305期:超级震撼数码管瀑布,使用OpenAI生成单片机游戏代码的可玩性,120通道逻辑分析仪,复古电子设计,各种运动轨迹函数源码实现
  • 力扣-查找每个员工花费的总时间
  • 企业级信息系统开发学习笔记1.8 基于Java配置方式使用Spring MVC
  • 【C语言复习】C语言中的文件操作
  • 00后整顿职场,当摸鱼测试员遇上了内卷00后。
  • 程序员的上帝视角(4)——视角
  • 一、webpack基础