今日头条 2018 AI Camp 6月2 日在线笔试编程题第一道——最大连续区间和扩展

阅读文本需要大概 2. 2 分钟

题目

给出一个长度为 n 的数组a1、a2、...、an，请找出在所有连续区间 中，区间和最大同时这个区间 0 的个数小于等于 3 个，输出这个区间和。

输入描述：

第一行一个正整数 n, 表示数组长度，1

第二行 n 个正整数，a1a2...an，其中 -1e9 a1、a2、...、an

输出描述：

一个整数

示例1：

输入

5

1 2 3 4 5

输出

15

示例2：

输入

6

15 0 0 0 0 20

输出

20

思路：

此问题为最大连续区间和的扩展，多增加了一个区间内 0 的个数不超过 3 的限制。 可以利用动态规划或者最简单的线性方法先解决最大区间和问题，再附加一个判断即可。

代码实现

文章仅为个人见解，如有错误，欢迎交流与指正！

你的点赞和转发就是对我最大的支持！