1、连续子数组的最大和（动态规划）

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。 数据范围： 1≤ n ≤2×10⁵ -100 ≤ a[i] ≤ 100

解答要求

时间限制: C/C++ 1000ms, 其他语言：2000ms 内存限制: C/C++ 256MB, 其他语言：512MB

样例

输入：[1,-2,3,10,-4,7,2,-5]

输出：18

解释：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

解答

要求所有子数组的和的最大值，可以这样思考，假设得到最大和的子数组以nums[i]结尾，那么就有两种情况：

1. 以nums[i-1]结尾的最大子数组（设为​）之和 > 0，此时的结果为[​]

2. 以nums[i-1]结尾的最大子数组（设为​）之和 <= 0，此时的结果为[​]

那么可以发现，要求得以nums[i]结尾的最大子数组，只要求出以nums[i-1]结尾的最大子数组就可以判断并计算了，因此考虑使用动态规划，用dp[i]表示以nums[i]结尾的最大子数组之和，可以列出状态转移方程如下：

以第一个元素结尾的最大子数组即为它本身，因此置dp[0]为0

def func():
    nums = input()[1:-1].split(',')
    mx = -100
    n = len(nums)
    dp = [0 for _ in nums]
    dp[0] = int(nums[0])
    if n == 1:
        print(nums[0])
        return
    
    for i in range(1, n):
        num = int(nums[i])
        dp[i] = max(dp[i-1] + num, num)
        if dp[i] > mx:
            mx = dp[i]
    
    print(mx)

if __name__ == "__main__":
    func()

2、查找输入整数二进制中1的个数(位运算)

输入一个正整数，计算它在内存中存储时 1 的个数。 注意多组输入输出！！！！！！ 数据范围： 1 ≤ n ≤ 2³¹−1

解答要求

时间限制: C/C++ 1000ms, 其他语言：2000ms 内存限制: C/C++ 256MB, 其他语言：512MB

输入

输入一个整数

输出

计算整数二进制中1的个数

样例

样例1

输入：5

输出：2

解释：5的二进制表示是101，有2个1

样例2

输入：0

输出：0

解答

本题为基础位运算题目，只需对输入循环进行对2取模（如果取模结果为1，说明此时最低位为1，计数+1）、整除2操作即可，直到数字为0，代码如下：

def func():
    count = 0
    num = int(input())
    while num != 0:
        if num % 2 == 1:
            count += 1
        num = num // 2
    print(count)

if __name__ == "__main__":
    func()

3、坐标移动（字符串）

开发一个坐标计算工具，A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从 (0,0) 点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。 输入： 合法坐标为A(或者D或者W或者S) + 数字（两位以内） 坐标之间以;分隔。 非法坐标点需要进行丢弃。如AA10;A1A; ;YAD; 等。

下面是一个简单的例子如： A10;S20;W10;D30;X;A1A;B10A11;;A10;

处理过程： 起点(0,0) + A10 = (-10,0) + S20 = (-10,-20) + W10 = (-10,-10) + D30 = (20,-10) + x = 无效 + A1A = 无效 + B10A11 = 无效 + 一个空 不影响 + A10 = (10,-10) 结果 (10，-10) 数据范围：每组输入的字符串长度满足1 <= n <= 10000，坐标保证满足-2^31 <= x，y <= 2^31-1，且数字部分仅含正数

输入

一行字符串

输出

最终坐标，以逗号分隔

样例

样例1：

输入：A10;S20;W10;D30;X;A1A;B10A11;;A10;

输出：10,-10

样例2：

输入：ABC;AKL;DA1;

输出：0,0

解答

首先分割字符串，然后分别判断方向和距离是否合法，即方向必须在'ADWS'中，距离必须为两位，且均为数字，不合法直接continue即可，合法则根据方向计算坐标，代码如下：

def func():
    x, y = 0, 0
    ops = input()[:-1].split(";")
    for op in ops:
        if not 2 < len(op) < 3:
            continue
        direction = op[0]
        if direction not in 'ADWS':
            continue
        
        is_digit = True
        for c in op[1:]:
            if c not in '0123456789':
                is_digit = False
        if not is_digit:
            continue
            
        num = int(op[1:])
        if direction == 'A':
            x -= num
        elif direction == 'S':
            y -= num
        elif direction == 'W':
            y += num
        elif direction == 'D':
            x += num
            
if __name__ == "__main__":
    func()
    

总结

总的来说，这次机考试题难度不大，在做题时需要考虑好边界情况，并且需要考虑代码有没有处理到所有的情况。第一题如果没有思路，可以先在纸上多写几个用例，观察结果与每个数的关系，考虑是否能够进行问题分解。想要机试拿高分，平时动态规划的题目是一定要多刷的。