k-concatenation-maximum-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer array <code>arr</code> and an integer <code>k</code>, modify the array by repeating it <code>k</code> times.

For example, if <code>arr = [1, 2]</code> and <code>k = 3 </code>then the modified array will be <code>[1, 2, 1, 2, 1, 2]</code>.

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be <code>0</code> and its sum in that case is <code>0</code>.

As the answer can be very large, return the answer modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: arr = [1,2], k = 3
Output: 9
</pre>

Example 2:

<pre>
Input: arr = [1,-2,1], k = 5
Output: 2
</pre>

Example 3:

<pre>
Input: arr = [-1,-2], k = 7
Output: 0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= 105</code></li>
	<li><code>-104 &lt;= arr[i] &lt;= 104</code></li>
</ul>

kConcatenationMaxSum

K-Concatenation Maximum Sum

Array

Dynamic Programming

给定一个整数数组&nbsp;<code>arr</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，通过重复&nbsp;<code>k</code>&nbsp;次来修改数组。

例如，如果&nbsp;<code>arr = [1, 2]</code>&nbsp;，<meta charset="UTF-8" />&nbsp;<code>k = 3</code>&nbsp;，那么修改后的数组将是 <code>[1, 2, 1, 2, 1, 2]</code> 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 <code>0</code>，在这种情况下它的总和也是 <code>0</code>。

由于&nbsp;结果可能会很大，需要返回的<meta charset="UTF-8" />&nbsp;<code>109&nbsp;+ 7</code>&nbsp;的&nbsp;模&nbsp;。

&nbsp;

示例 1：

<pre>
输入：arr = [1,2], k = 3
输出：9
</pre>

示例 2：

<pre>
输入：arr = [1,-2,1], k = 5
输出：2
</pre>

示例 3：

<pre>
输入：arr = [-1,-2], k = 7
输出：0
</pre>

&nbsp;

提示：
<meta charset="UTF-8" />

<ul>
	<li><code>1 &lt;= arr.length &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= 105</code></li>
	<li><code>-104&nbsp;&lt;= arr[i] &lt;= 104</code></li>
</ul>