[Python3] Clear code & Explanation to hint 4 & Explanation with figures
The hardest part of this problem is to understand why hint 4: "The answer is the maximum between, the answer for k=1, the sum of the whole array multiplied by k
The hardest part of this problem is to understand why **hint 4**: "*The answer is the maximum between, the answer for k=1, the sum of the whole array multiplied by k, or the maximum suffix sum plus the maximum prefix sum plus (k-2) multiplied by the whole array sum for k > 1.*" is correct.\n\nLet\'s analyze 3 cases:\n1. When ```k=1```, the problem is reduced to implementing the Kadane Algorithm, as mentioned in many other posts.\n2. When ```k=2```, there are two subcases:\n2.1. some suffix and prefix form the maximum, as illustrated below:\n![image](https://assets.leetcode.com/users/images/7c26b9ca-0b36-4fdb-b13d-c7641ab5aa5a_1617256542.4299235.png)\n2.2. the second array has no contribution (i.e. same as when k=1). For example, ```[-1, -1, 1, -1, -1, 1]```, the maximum subarray is ```[1]```, adding the second half won\'t make it better.\n3. When ```k>=3```, besides the two subcases aforementioned in 2.1 and 2.2, there\'s a third possibility, where the middle ```(k-2)``` arrays have positive contributions:\n![image](https://assets.leetcode.com/users/images/93d7b8f1-63c3-4dcf-ad6b-8947d2de9a7c_1617257041.715272.png)\nYou may ask why ```k-2```? Can\'t it be ```k-3, k-4,...``` ? This is because under the assumption that each array has positive contribution to the sum, adding ```k-2``` positive sums is obviously better than other choices.\n\nCode:\n```\ndef kConcatenationMaxSum(arr: List[int], k: int) -> int:\n\tMOD = 10**9 + 7\n\n\tdef kadane(arr):\n\t\tmax_local = 0\n\t\tmax_global = float("-inf")\n\t\tfor i in range(len(arr)):\n\t\t\tmax_local = max(max_local+arr[i], arr[i])\n\t\t\tmax_global = max(max_global, max_local)\n\t\treturn max(0, max_global)\n\n\tdef prefixSum(arr):\n\t\tmax_global = float("-inf")\n\t\ts = 0\n\t\tfor i in range(len(arr)):\n\t\t\ts += arr[i]\n\t\t\tmax_global = max(max_global, s)\n\t\treturn max_global\n\n\tm1 = kadane(arr)\n\tm2, m3 = prefixSum(arr), prefixSum(arr[::-1])  # prefix sum and suffix sum\n\ts = sum(arr)\n\n\tif k == 1:\n\t\tans = m1\n\telif k == 2:\n\t\tans = max(m2+m3, m1)\n\telse:\n\t\tans = max(max(m2+m3, m1), m2+m3+(k-2)*s)\n\n\treturn ans % MOD\n```
[]