TomoLink
CompaniesZeptoData Structures & AlgorithmsK-Concatenation Maximum Sum
DSA
MediumArray

K-Concatenation Maximum Sum

arraydynamic programming

Problem Statement

Given an integer array arr and an integer k , modify the array by repeating it k times.

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

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

As the answer can be very large, return the answer modulo 10 ^9 + 7 .

Examples

Example 1
Input: arr = [1,2], k = 3
Output: 9
Example 2
Input: arr = [1,-2,1], k = 5
Output: 2
Example 3
Input: arr = [-1,-2], k = 7
Output: 0

Constraints

1 <= arr.length <= 10 ^5
1 <= k <= 10 ^5
-10 ^4 <= arr[i] <= 10 ^4
🤔
Medium
Difficulty
Topic Info
ModuleDSA
CategoryArray
Sub-topicDynamic Programming
Tags
arraydynamic programming
Navigation
K-Concatenation Maximum Sum [Medium] | Zepto Dsa | TomoLink