涂鸦移动2021校招软件工程师测试题

博主于2020.9.13日参加了涂鸦移动软件工程师的笔试，奈何实力不够，只解出了一道题，这些题网络上并没有原题，剩余两道我也会放上来（大佬们做出来可以放在评论区，或联系我注明版权放在博客中）与大家分享：

（*所有题目均使用标准输入输出）

• 测试题1

现有一个整形数组，你可以重新排列数组中的元素，也可以任意删除元素，使得新数组a按照以下公式：Sum = ∑a [i]*(i+1) 计算的和最大。

例：
输入:[-2,-5,0,4,-7]
输出:10
解释:新数组为[-2, 0, 4]，sum = -21 + 02 + 4*3 = 10

输入:[-1,-2,-3]
输出:0
解释：新数组为[]，sum = 0

思路：利用动态规划的思想，加之暴力破解，详细讲解观看代码注释即可

• 测试题2

有一台破旧的打字机，用该打字机打印的字符串中所有的m都变成了nn，w都变成了uu。
现在给你一串该打印机打印出来的字符串，请问有多少种可能的原始串br> 因结果可能超过整形范围，请输出结果除以109+7的余数。
如果结果中出现了不可能出现的字符（m或者w），输出0。

输入格式：仅一行，内容为打字机输出的字符串。
输出格式：仅一行，可能的原始字符串数量模10^9+7

例：
输入:suukinni
输出:4
解释:共四种可能的原串：suukinni，swkimi，suukimi，swkinni

输入:ueueue
输出:1

输入:uuu
输出:3
解释:共三种可能的原串：uuu，uw，wu

输入:mako
输出:0
解释:包含了不可能出现的字符m

• 测试题3

测试题3：有一个整型数组，找到一个连续子序列，允许在子序列中最多删除两个元素后（删除后不能为空），这个子序列的和最大，返回这个最大的和。

例：
输入:[ 1, 1, -2,3]
输出:5
解释：选择子序列[1, 1, -2,3]，删除-2，最大和为5

输入: [-1,-1,-2,-1]
输出:-1
解释：选择子序列[-1]，最大和为-1

输入: [1,-2, 2,1,-2,-5,2]
输出:5
解释：选择子序列[2,1,-2,-5,2]，删除-2,-5，最大和为5

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34686 人正在系统学习中

来源：南窗木心