小米2013校园招聘笔试题-最大连续子序列乘积
序列 最大 2013 小米 笔试 连续 招聘 校园
2023-09-27 14:23:51 时间
九度题目地址:http://ac.jobdu.com/problem.php?pid=1501
- 题目描述:
-
给定一个浮点数序列(可能有正数、0和负数),求出一个最大的连续子序列乘积。
- 输入:
-
输入可能包含多个测试样例。
每个测试样例的第一行仅包含正整数 n(n<=100000),表示浮点数序列的个数。
第二行输入n个浮点数用空格分隔。
输入数据保证所有数字乘积在双精度浮点数表示的范围内。
- 输出:
-
对应每个测试案例,输出序列中最大的连续子序列乘积,若乘积为浮点数请保留2位小数,如果最大乘积为负数,输出-1。
- 样例输入:
-
7 -2.5 4 0 3 0.5 8 -1 5 -3.2 5 -1.6 1 2.5 5 -1.1 2.2 -1.1 3.3 -1.1
- 样例输出:
-
12 64 8.78
进入了误区,想了好久怎么区分正负情况。最后发现还是不区分方便,不管正负一律计算两次。一个保存最大值,一个保存最小值。
负数越小,绝对值就越大。
(暴力解决的时间复杂度n^2,肯定会超时!)
#include<iostream> #include<stdio.h> #include<math.h> using namespace std; double d1, d2; //分别保存最大值和最小值 int n; double ans, d, tmp1, tmp2; int main() { while (~scanf("%d", &n)) { scanf("%lf", &d1); ans = d2 = d1; for (int i = 1; i < n; i++) { scanf("%lf", &d); tmp1 = d1 * d; tmp2 = d2 * d; d1 = max(max(tmp1, tmp2), d); d2 = min(min(tmp1, tmp2), d); if (d1 > ans) ans = d1; } int t = (int) ans; if (ans < 0) { puts("-1"); } else { if (ans == t) printf("%d\n", t); else printf("%.2f\n", ans); } } }
相关文章
- Python 时间序列异常点检测 | tsmoothie 基于数据平滑/拟合的方法 简单却快速有效
- Informer讲解PPT介绍【超详细】--AAAI 2021最佳论文:比Transformer更有效的长时间序列预测
- 机器学习-概率图模型:最大熵马尔可夫模型(MEMM)【解决序列问题】【前提假设:隐层状态序列符合马尔可夫性】【HMM--去除“观测状态相互独立”假设-->MEMM】【判别式模型】
- 时间序列-预测-模型:LSTM【单特征/多特征】【利用前50个时间步的数值预测接下来的10个时间步的数值:(0-49)->50;(1-50此50为上一步预测出的)->51;(2-51)->52...】
- 时间序列-预测-模型-2021:SCINet
- NLP-基础任务-中文分词算法(3)-基于字:基于序列标注的分词算法【BiLSTM+CRF】
- 推荐模型-序列推荐-2019:FDSA
- 大数据-计算引擎-实时数据分析框架:SparkStreaming【DStream编程(Discretized Stream);一个 DSteam 是由一连串 RDD 序列组成;准实时(秒级别)】
- mysql时间序列与窗口函数
- HDU1231 最大连续子序列和
- 53. Maximum Subarray 最大子序列和
- LeetCode_数学推导_困难_891.子序列宽度之和
- LeetCode_回溯_中等_491.递增子序列
- LeetCode_动态规划_中等_1143.最长公共子序列
- 最大连续子序列 (HDU - 1231)
- 剑指offer-21.栈的压入弹出序列
- NLP自然语言处理系列-时间序列数据分析-趋势性、周期性、自相关性、冲量、差分、移动平均误差计算
- 十二周项目三(4)——出口fibnacci第一序列20的数量
- BLAST - 序列数据库搜索
- 【译】使用 LINQ 合并 IEnumerable 序列
- 【ybtoj高效进阶 21274】相似序列(主席树)(哈希)(二分)
- leetcode 300 最长递增子序列
- leetcode 673 最长递增子序列的个数