AmazonOA #37

Calculate Max Quality Score

估计中等可在线判题

You are given an integer array ratings and a positive integer impactFactor. You must choose a non-empty contiguous range exactly once and either multiply all of its elements by impactFactor, or divide all of them by impactFactor, rounding toward 0 (down for positive numbers, up for negative numbers). Only one of the two strategies may be used. After the operation, choose a non-empty contiguous subarray of the whole array; its element sum is the quality score. Find the maximum achievable quality score. The modified range and the final scored range do not need to be the same.

This site's standard input and merged ranges: 1≤n≤200000, 1≤impactFactor≤10000, −10^9≤ratings[i]≤10^9. The complete raw source gives n≤200000, |ratings[i]|≤100000; the catalog gives n≤100000, |ratings[i]|≤10^9 and does not keep the factor range. This site takes the envelope of the two ranges and adopts the positive-integer factor range from raw, without claiming these are the original raw constraints.

输入格式

The first line contains n impactFactor; the second line contains n integers ratings[i].

输出格式

Output one integer, the maximum non-empty contiguous subarray sum after exactly one operation.

样例 1

输入：

5 2
5 -3 -3 2 4

输出：

样例 2

输入：

5 3
5 -3 -3 2 4

输出：

样例 3

输入：

4 1
-2 3 -3 -1

输出：

样例 4

输入：

1 2
-5

输出：

-2

样例说明

Example 1: multiplying the last two items gives 4 and 8, so the answer is 12. Example 2: the same array with factor 3; multiplying the last two items gives 6 and 12, so the answer is 18, which corrects the 12 the catalog originally wrote by mistake. Example 3: a factor of 1 does not change the array, so the answer is 3. Example 4: dividing −5 by 2 toward 0 gives −2.