codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1899C.md (1464B)


      1 Source: https://codeforces.com/problemset/problem/1899/C
      2 
      3 C. Yarik and Array
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A subarray is a continuous part of array.
     22 
     23 Yarik recently found an array $a$ of $n$ elements and became very interested in finding the maximum sum of a non empty subarray. However, Yarik doesn't like consecutive integers with the same parity, so the subarray he chooses must have alternating parities for adjacent elements.
     24 
     25 For example, $[1, 2, 3]$ is acceptable, but $[1, 2, 4]$ is not, as $2$ and $4$ are both even and adjacent.
     26 
     27 You need to help Yarik by finding the maximum sum of such a subarray.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ $(1 \le t \le 10^4)$ — number of test cases. Each test case is described as follows.
     32 
     33 The first line of each test case contains an integer $n$ $(1 \le n \le 2 \cdot 10^5)$ — length of the array.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(-10^3 \le a_i \le 10^3)$ — elements of the array.
     36 
     37 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the answer to the problem.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 7
     49 
     50 5
     51 
     52 1 2 3 4 5
     53 
     54 4
     55 
     56 9 9 8 8
     57 
     58 6
     59 
     60 -1 4 -1 0 5 -4
     61 
     62 4
     63 
     64 -1 2 4 -3
     65 
     66 1
     67 
     68 -1000
     69 
     70 3
     71 
     72 101 -99 101
     73 
     74 20
     75 
     76 -10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 15
     83 17
     84 8
     85 4
     86 -1000
     87 101
     88 10
     89 ```