[Python3] Kadane Algorithm
Intuition\nLongest continuos sum of sub-array containing negative number -> Kadane algorithm\n Describe your first thoughts on how to solve this problem. \n\n# 
# Intuition\nLongest continuos sum of sub-array containing negative number -> Kadane algorithm\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe can iterate all over the arr `k` times and do kadane in it. It will work perfectly but not smart enough to pass all test cases. You will meet TLE in some cases. Even Kadane is smart but this way can be considerer brute-force with ones who\'ve already knew about Kadane.\n\nKadane is a greedy algorithm but with this cases we can do it more greedily to avoid iterate the arr `k` times.\nTo do it there are 2 cases that can return the max sum that we should consider:\n- Taking the whole arr k-th times and sum it.\n- Taking 1 semgment of sub-array that length is smaller than length arr * k\n- Then we should find the maximum between 2 cases.\n\nWhy it should work:\n- first of all we take all array if and only if sum of an array is positive (think it greedily). If it is negative we cannot take it we can only take segment of sub-array to get the max. With this we just need to calculate the sum of `arr` and sum it `k` times.\n- Consider this example: `arr` = `[0,0,3,9,-2,-5,4]` and `k` = 5. You can see the `sum` of `arr` is `9` so the max sum is 9 * 5 = 45 (correct answer).\n- What about this cases: `arr` = `[-5,-2,0,0,3,9,-2,-5,4]` and `k` = 5. `sum` of `arr` is `2` but the sum is not 2 * 5 like before. it is 9 + 2 * 4 = 17. How to find that we see that if we choose to take the whole array we always have to take the next `k-1` sub-array and max end part of the 1st array. The max end part of 1st sub-array can be find by kadane and you can find it `9` that why we have `9 + 2 * 4`\n- You may say that the maximum sum get from kadane for the first array does not come from the ending sub-array of the first array to make it continuos with the left but it does since we apply this equation with non-negative sum of array.\n- There are also a case the sum of whole sub-array is smaller than the sum of segment of sub-array. You can think about that if sum of array is positive but small and `k` is small too -> for example sum array is 1 and k is 2 -> if we apply the above equation the answer will be 2 It is failed in this case. `arr` = `[-1,1,2,3,-8,4]` and `k` = `2`. `sum` of `arr` is `1` which is positive so if we take all elements the `max_sum` is 1 * 2  = 2. However if we take only subarray the `max_sum` will be bigger. let see this array repeat 2 times will be `[-1,1,2,3,-8,4,-1,1,2,3,-8,4]` -> if we take sub-array from the 1st index (0-based index) to the 9th index the sum will be:\n1 + 2 + 3 - 8 + 4 - 1 + 1 + 2 + 3 = 7. And yeah `7` is the correct answer in this case\n- Thus we only need to care about 2 cases as I said which can minimize a lot of calulation.\n- For the case getting sub-array. It can be from only one array or it can come from 2 consecutive array. With k=1 we can only check from only 1 array that is why I use `min(k, 2)`\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n        s, mod = sum(arr), 10 ** 9 + 7\n        n = len(arr)\n\n        def kadane(l: int) -> int:\n            cur_s = max_s = 0\n            for i in range(l):\n                num = arr[i % n]\n                cur_s = max(0, cur_s + num)\n                max_s = max(max_s, cur_s)\n            return max_s\n\n        if s > 0: return max((kadane(n) + s * (k - 1)), kadane(n * min(k, 2))) % mod\n```
['Array', 'Dynamic Programming', 'Python3']