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

【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)

【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)

前言

Problem:1007 Maximum Subsequence Sum (25 分)

Tags:DP

Difficulty:剧情模式 想流点汗 想流点血 死而无憾

Address:1007 Maximum Subsequence Sum (25 分)

问题描述

求最大连续子序列和,输出这个连续子序列的首值、尾值和序列和(优先最靠前的),如果都为这个序列都为负的输出0和整个序列的首尾值。

解题思路

  1. 一道经典又特殊的动态规划,本身很简单,但考虑到要求最靠前的首尾值,容易出错,难度相应提高。
  2. dp[i]dp[i]dp[i] 表示以 N[i]N[i]N[i] 为结尾的最大连续子序列和,再用一个 pos[i]pos[i]pos[i] 表示这个子序列的首位置。
  3. 优化:由于dp访问的单调性,可以压缩空间,用一个dp值和pos值代替这俩个数组。

参考代码

1. 未压缩空间:

#include<iostream>
#include<vector>using namespace std;
int K; // K integers  1e4
vector<int> N;
vector<int> dp, start_index;
int maxi;void init() {cin >> K;N.resize(K, 0);dp.resize(K, 0);start_index.resize(K, 0);for (int i = 0; i < K; ++i) {cin >> N[i];}}void do_dp() {maxi = 0;dp[0] = N[0];start_index[0] = 0;for (int i = 1; i < K; i++) {if (dp[i - 1] >= 0) {dp[i] = dp[i - 1] + N[i];start_index[i] = start_index[i - 1];} else {dp[i] = N[i];start_index[i] = i;}maxi = dp[i] > dp[maxi] ? i : maxi;}
}void solution_1007() {init();do_dp();if (dp[maxi] < 0) {cout << 0 << " " << N[0] << " " << N[K - 1] << endl;return;}cout << dp[maxi] << " " << N[start_index[maxi]] << " " << N[maxi] << endl;
}
int main() {solution_1007();return 0;
}

2. 压缩空间:

(参考柳神 https://github.com/liuchuo/PAT/tree/master/AdvancedLevel_C++ )

这么写后竟然奇妙的发现当所有值都是负的时 leftindex 、rightindex会保持初始值,总而言之精简了很多,膜拜 orz。

#include<iostream>
#include<vector>using namespace std;
int K; // K integers  1e4
vector<int> N;
int dp, temp_start_index, left_index, right_index;
int maxx;void init() {cin >> K;N.resize(K, 0);for (int i = 0; i < K; ++i) {cin >> N[i];}}
void do_dp() {maxx = -1;dp = 0;temp_start_index = 0;left_index = 0;right_index = K - 1;for (int i = 0; i < K; i++) {// 注意从上一个循环继承来的 dp 值永远不会小于0,给原 dp 值加上 N[i] 后再判断dp = dp + N[i];if (dp < 0) {  // 加上 N[i] 后 dp 小于0了,只可能因为 N[i] 为负数dp = 0;temp_start_index = i + 1;} else if (dp > maxx) { // 获得更大子串和maxx = dp;left_index = temp_start_index;right_index = i;}}
}void solution_1007() {init();do_dp();if (maxx < 0) {maxx = 0;}cout << maxx << " " << N[left_index] << " " << N[right_index] << endl;
}
int main() {solution_1007();return 0;
}

总结

对于这种会保存下标的题,coding时不要分心写错了,一开始把 pos_start[i] = i 写成了 pos_start[i] = N[i],由于样例能过检查了好久才找出来(情人节不适合code)。

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

相关文章:

  • 华为OD机试真题Python实现【 最小叶子节点】真题+解题思路+代码(20222023)
  • mars3d动态轨迹DynamicRoamLine,如何获取实时运⾏的经纬度
  • jvm常识
  • PHP部署、nginx与PHP的整合、PHP动态添加模块
  • SpringCloud与SpringBoot的版本对应
  • 华为OD机试题,用 Java 解【N 进制减法】问题
  • Linux->进程概念于基本创建
  • 【MySQL】5.7版本解压安装配置
  • c++类对象数据成员和虚函数的内存布局
  • Python 模块和包
  • Java零基础专栏——面向对象
  • 离散无记忆与有记忆信源的序列熵
  • 算法该不该刷?如何高效刷算法?
  • Allegro如何在关闭飞线模式下查看网络连接位置操作指导
  • 啊哈 算法读书笔记 第 1 章 一大波数正在靠近——排序
  • Servlet笔记(5):HTTP请求与响应
  • 信号的运算与变换
  • 【GO】K8s 管理系统项目9[API部分--Secret]
  • ESP32 Arduino EspNow点对点双向通讯
  • Linux SID 开发指南
  • Matlab进阶绘图第2期—线型热图
  • 【Redis中bigkey你了解吗?bigkey的危害?】
  • C++回顾(一)——从C到C++
  • CRF条件随机场 | 关键原理+面试知识点
  • 秒懂算法 | 回归算法中的贝叶斯
  • 用Netty实现物联网01:XML-RPC和JSON-RPC
  • 腾讯云服务器centos7安装python3.7+,解决ssl问题
  • C++【模板STL简介】
  • 该学会是自己找bug了(vs调试技巧)
  • Redis大全(概念与下载安装)