K-Concatenation Maximum Sum

MediumDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an integer array arr and an integer k, form a new array by writing arr out k times back to back (for example [1,2] with k = 3 becomes [1,2,1,2,1,2]). Return the maximum sum of a contiguous subarray of the concatenated array. The empty subarray is allowed, so the answer is never negative. Because the answer can be large, return it modulo 10^9 + 7 (take the true maximum first, then the remainder).

Examples

Input: arr = [1,2], k = 3
Output: 9
The whole array `[1,2,1,2,1,2]` sums to 9.
Input: arr = [1,-2,1], k = 5
Output: 2
Taking `[1,1]` across the boundary between two copies gives 2; the total of one copy is 0, so more copies do not help.
Input: arr = [-1,-2], k = 7
Output: 0
Every element is negative, so the empty subarray is best.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= k <= 10^5
  • -10^4 <= arr[i] <= 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems