今日头条 2018 AI Camp 6 月 2 日在线笔试编程题第一道——最大连续区间和扩展
2021/6/10 14:21:16
本文主要是介绍今日头条 2018 AI Camp 6 月 2 日在线笔试编程题第一道——最大连续区间和扩展,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给出一个长度为 n 的数组a1、a2、...、ana1、a2、...、an,请找出在所有连续区间 中,区间和最大同时这个区间 0 的个数小于等于 3 个,输出这个区间和。
-
输入描述:
第一行一个正整数 n, 表示数组长度,1 <= n <= 1000000。
第二行 n 个正整数,a1a2...ana1a2...an,其中 -1e9 <= a1、a2、...、ana1、a2、...、an <= 1e9 -
输出描述:
一个整数 -
示例1:
输入
5
1 2 3 4 5
输出
15 -
示例2:
输入
6
15 0 0 0 0 20
输出
20 -
思路:
此问题为最大连续区间和的扩展,多增加了一个区间内 0 的个数不超过 3 的限制。 可以利用动态规划或者最简单的线性方法先解决最大区间和问题,再附加一个判断即可。
-
代码实现
#include <iostream> using namespace std; int MaxSubArray(int nums[], int n); int main() { int n = 0; cin >> n; int num[n]; for(int i = 0; i < n ; i++) { cin >> num[i]; } cout << MaxSubArray(num, n); } int MaxSubArray(int num[], int n) { int i = 0, sum = 0, max_sum = 0; int temp_sum[4] = {0}; int temp = 0; int zero_num = 0; for(i = 0; i < n; i++) { sum += num[i]; /* 累加求和,只要和非负,就不会使得再相加的和变小,也就是对和的增加有贡献,就可以继续累加 */ if(num[i] == 0) { zero_num++; temp_sum[zero_num-1] = sum; /*保存每次遇到 0 时的区间和*/ } /* 增加一个对区间内 0 个数的判断 */ if(sum > max_sum && zero_num <= 3) { max_sum = sum; } /*和为负,清零,重新开始*/ if(sum < 0) { sum = 0; zero_num = 0; temp_sum[0] = 0; temp_sum[1] = 0; temp_sum[2] = 0; temp_sum[3] = 0; } /*遇到第四个 0 时对区间和进行更新,以第一个 0 后的数作为起点重新开始*/ if(zero_num > 3) { zero_num -= 1; sum = sum - temp_sum[0]; temp = temp_sum[0]; temp_sum[0] = temp_sum[1] - temp; temp_sum[1] = temp_sum[2] - temp; temp_sum[2] = temp_sum[3] - temp; temp_sum[3] = sum; } } return max_sum; }
个人见解,如有错误,欢迎指正与交流!
这篇关于今日头条 2018 AI Camp 6 月 2 日在线笔试编程题第一道——最大连续区间和扩展的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享