Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: K-Concatenation Maximum Sum

Posted on February 10, 2020July 26, 2020 by braindenny

K-Concatenation Maximum Sum



Similar Problems:

  • CheatSheet: LeetCode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #kadane

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.

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
## https://code.dennyzhang.com/k-concatenation-maximum-sum
## Basic Ideas: Kadane
##
##  If we include one repeition of the list, we can include all
##
## Complexity: Time O(n), Space O(1)
class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        totalSum = sum(arr)
        res = 0
        if totalSum >= 0:
            res = totalSum*(max(0, k-2))

        nums = [0]*n
        if k > 1:
            nums = [0]*2*n
            for i in range(n):
                nums[i] = arr[i]
                nums[i+n] = arr[i]
        else:
            for i in range(n):
                nums[i] = arr[i]

        # Kadane
        maxSum = -sys.maxsize
        maxSoFar = 0
        for i in range(len(nums)):
            v = nums[i]
            maxSoFar = max(v, maxSoFar+v)
            maxSum = max(maxSum, maxSoFar)

        res += maxSum
        return max(res, 0) % (10**9+7)
linkedin
github
slack

Post Views: 0
Posted in MediumTagged kadane

Post navigation

LeetCode: Number of Submatrices That Sum to Target
LeetCode: Top Travellers

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.