1822: STEMA-C-5 交替序列

提示信息： 

子序列:对于一个序列 a，删除其中 0 个或多个元素而不改变剩余元素的顺序，得到的序列称为 a 的子序 列。 

例如:序列 a 为 {1，2，3，4，5}，则序列 {1}，{1，2，3}，{1，3，5} 等都可以称为序列 a 的子序列。 

题目描述： 

给定一个包含n个整数的序列a，请从中找出一个满足以下条件的子序列： 

1）该子序列中相邻元素的正负号相反（如果第一个元素为正数，则第二个元素为负数，第三个元素为正数，以此类推。

反之，如果第一个元素为负数，则第二个元素为正数，第三个元素为负数，以此类推）； 

2）该子序列长度最长； 

3）在满足以上条件的情况下，该子序列中的元素之和最大。 

最后输出该子序列中的元素之和。 

例如:n = 5;序列 a 为 {2，-1，-3，15，10}。 

同时满足条件 1 和条件 2 的子序列有 {2，-1，15}，{2，-1，10}，{2，-3，15}，{2，-3，10}; 

其中元素之和最大的子序列是 {2，-1，15}，和为 16。

第一行输入一个整数n（1≤n≤2×105）； 

第二行输入n个整数a（-109i≤ai≤109，ai≠0），整数之间以一个空格隔开。

5
2 -1 -3 15 10

16