PAT 甲级 1007. Maximum Subsequence Sum (25) 【最大子串和】
2024-09-04 14:56:43
题目链接
https://www.patest.cn/contests/pat-a-practise/1007
思路
最大子列和
就是 一直往后加 如果 sum < 0 就重置为 0
然后每次 判断一下 sum 是否 > ans
如果是 就更新
然后 为什么这样是对的
就是 假设 当前数字是最大子串和 我们如何知道 前面的求和结果 要不要放入当前子串中 如果前面的求和结果 < 0 的话 那么对当前子串 是没有贡献的 所以就不要
然后 我们需要记录 子串的起始位置 就可以了
因为 更新答案的时候 当前位置 就是结束位置
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int MOD = 1e9 + 7;
int arr[maxn];
int main()
{
int n;
cin >> n;
int l, r, ans = -1, num, temp = 0, vis, flag = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
if (i == 0 || flag)
{
vis = arr[i];
flag = 0;
}
temp += arr[i];
if (temp < 0)
{
temp = 0;
flag = 1;
continue;
}
if (temp > ans)
{
ans = temp;
l = vis;
r = arr[i];
}
}
if (ans != -1)
printf("%d %d %d\n", ans, l, r);
else
printf("%d %d %d\n", 0, arr[0], arr[n - 1]);
}
最新文章
- db2学习笔记--数据类型对表的影响
- Neutron 功能概述 - 每天5分钟玩转 OpenStack(65)
- win10 下 gulp-sass 无法使用的解决
- java中Comparable实现对象的比较
- 2101 Problem A Snake Filled
- 根据数据库输出XML菜单
- Spark运行在eclipse_使用PyDev和pyspark
- K2上海总部技术培训分享笔记
- PHP最佳实践(译)
- pb popmenu弹出式选单位置的问题
- SQL Server 2008 R2 制作数据库结构和数据脚本
- JS中timestamp日期类型的转换
- js 去掉字符串最后一个字符
- 为学Linux,我看了这些书
- 团队作业4——第一次项目冲刺(ALpha版本)第三天
- Opengl4.5 中文手册—F
- java调用c++函数的简单笔记
- Stripe Compaction
- WCF开发框架形成之旅--个人图片信息的上传保存
- Spring Boot+MyBabits静态连接多个数据库
热门文章
- tomcat部署不成功 Deployment failure on Tomcat 6.x. Could not copy all resources to
- Ubuntu下sudo apt-get install vim 失败的解决办法
- Ambient Occulution
- 过滤器Filter_03_多个Filter的执行顺序
- dubbo zookeeper案例
- Python标准库:1. 介绍
- pymongo的基本使用
- MySQL 函数笔记
- Web安全系列(二):XSS 攻击进阶(初探 XSS Payload)
- spring-struts-mybatis整合错误集锦