Codeforces 1343C - Alternation S

夜里的车站，这是旅程中拍的一张照片，这一站只有我一个人上车，一个列车员值岗。生活的便利都是这样默默无闻的人创造的吧？在看不见的地方。

题目: Codeforces 1343C - Alternation Subsequence

https://codeforces.com/problemset/problem/1343/C

翻译

题目是交替的队列。

先定义一个概念“子串”，子串就是从一个数列中删除0个、1个或者多个元素不改变队列顺序，得到的串就是子串。

交替的子串就是要求串内没有连续的正数或者负数。

要求得到最长交替的子串中串内元素和最大的子串，要求输出这个和的值。

要点就是要求是最长交替的子串，并且要求和最大。

输入格式

输入值 t 表示测试组数，接下来输入 t 组测试数据

输入值 n 表示有多少个数字，接下来一行输入 n 个数字，数字间用一个空格分隔，保证输入的数字只有正整数和负整数，保证没有 0。

输出格式

输出最长交替的子串最大和。

分析

最长交替的子串，一定是正负数交替的次数，这是可以直观看出的。也就是将连续的正数和负数中分别取出最大值相加就是答案。

解法很好理解，为了方便处理，我将得到的数列尾部添加了一个0，用于快捷处理最后那个数字的逻辑。理论上说代码可以更短，碍于水平的限制，就只能这样了。

代码(Python3)

# https://codeforces.com/problemset/problem/1343/C

import sys

# sys.stdin = open(r"./file/input.txt", 'r')
# sys.stdout = open(r"./file/output.txt", 'w')

t = int(input())

for _ in range(t):
    n = int(input())
    str = input()
    numbers = str.split(" ")
    numbers.append(0)
    last = None
    sum = 0
    for i in numbers:
        number = int(i)
        if last == None:
           last = number
        else:
            if (last < 0 and number < 0) or (last > 0 and number > 0):
                last = max(last, number)
            else:
                sum += last
                last = number
    print(sum)
```![37da91586edd250d0d1f57f322c6cd9.jpg](https://img.haomeiwen.com/i2060280/a0c51ecfc4ce2157.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

by 费城的二鹏 2020.05.02 白山