Javascript | K=1 2 and 3 reveals the logic
Step 1\nSolve how to get maximum sub array sum:\n\nExample:\n[4, -3, 1, -2, -1, 5]\nWe keep 2 variables MAX and CUR\n\nIterations\ni = 4: MAX = 4 and CUR = 4\ni
**Step 1**\nSolve how to get maximum sub array sum:\n```\nExample:\n[4, -3, 1, -2, -1, 5]\nWe keep 2 variables MAX and CUR\n\nIterations\ni = 4: MAX = 4 and CUR = 4\ni = -3: MAX = 4 and CUR = 1\ni = 1: MAX = 4 and CUR = 2\ni = -2: MAX = 4 and CUR = 0\ni = -1: MAX = 4 and CUR = 0 (if CUR<0 make it 0 again)\ni = 5: MAX = 5 and CUR = 5\n```\nIf at any point our CUR variable becomes negative we reset it back to 0 as we don\'t need our answer to be less than 0. Else we add it to cur variable because we might spot a greater sum than current one.\n\nThis is classic algorithm known as kadane, look it up on wikipedia\n\n```\nlet maxSum = function(ar){\n    let max = 0;\n    let cur = 0;\n    \n    for(let i of ar){\n        if(i+cur > 0)\n            cur+=i;\n        else\n            cur = 0;\n        max = Math.max(cur,max);\n    }\n    \n    return max;\n}\n```\n**Step 2**\nModulus operations. If you don\'t know why we apply mod for big valued answers, read about it.\nThe basic idea behind taking Mod is to prevent integer overflows\n```\nlet mod = 10**9+7;\n\nlet addMod = (a,b) => (a%mod + b%mod)%mod;\nlet mulMod = (a,b) => (a%mod * b%mod)%mod;\nlet subMod = (a,b) => (a%mod - b%mod)%mod;\n```\n**Step 3**\nSolving the problem:\nFor any problem which deals with a variable like k which is applied on a data structure try to iterate it manually for some values like (k=1, k=2, k=3)\n```\nObservation 1:\n[-1,-2] if all elements are -ve whatever the value of k is, the answer will be 0 always\n```\n```\nObservation 2:\n[1,3,1] if all elemets are +ve, the answer would be k*sum(ar)\n```\n\nIterate over some examples:\n```\nk = 1\n[3, -2, -2, 1]\nThe answer would be simply \'maximum sub array sum\' which would be 3 in this case\n```\n```\nk = 2\n[3, -2, -2, 1, 3, -2, -2, 1]\nHere, the answer would be 4 as array is doubled so the two positive integers at each end would come together.\n```\n```\nFor k = 3 the same would happen\n```\n\nThis was one example where the sum of negative elements was large enough to cancel out positives so we couldn\'t increase the window of our solution for k=2, 3 and so on.\n\n**Example 2:**\n```\nk = 1\n[4, -1, -1, 5, -1]\nanswer = 6\n```\n```\nk = 2\n[4, -1, -1, 5, -1, 4, -1, -1, 5, -1]\nanswer = 13\n```\n```\nk = 3\n[4, -1, -1, 5, -1, 4, -1, -1, 5, -1, 4, -1, -1, 5, -1]\nanswer = 19\n```\nIf you look closely, you will find that the answer is all about "till what extent we can increase our window of elements". This would form an arithmetic progression as we increase value of \'k\'.\nFor kth iteration value would be: a + (k-1)*diff\nwhere a is answer for k =1 and diff is the difference in progression\n\nTry iterating for array [-5, -2, 0, 0, 3, 9, -2, -5, 4]\n\nFrom above explanation we found out that there can be 2 cases overall:\n1. Max-subarray sum over different k follows arithemetic progression\n2. Max-subarray sum remains constant after k=2 as the window cannot be increased more.\n\nJust find out answes for k=1,2 and 3 and formulate the final answer accordingly.\n\nCode:\n```\n/**\n * @param {number[]} arr\n * @param {number} k\n * @return {number}\n */\n\nlet mod = 10**9+7;\n\nlet addMod = (a,b) => (a%mod + b%mod)%mod;\nlet mulMod = (a,b) => (a%mod * b%mod)%mod;\nlet subMod = (a,b) => (a%mod - b%mod)%mod;\n\nlet maxSum = function(ar){\n    let max = 0;\n    let cur = 0;\n    \n    for(let i of ar){\n        if(i+cur > 0)\n            cur+=i;\n        else\n            cur = 0;\n        max = Math.max(cur,max);\n    }\n    \n    return max;\n}\n\n\nvar kConcatenationMaxSum = function(ar, k) {\n    let ans1 = maxSum(ar)%mod\n    \n    if(k==1)\n        return ans1;\n    \n    let ar2 = [...ar, ...ar]\n    let ans2 = maxSum(ar2)%mod\n    \n    if(k==2)\n        return ans2;\n    \n    if(k>=3){\n        let ar3 = [...ar2, ...ar]\n        let ans3 = maxSum(ar3)%mod\n        let diff = subMod(ans3,ans2)\n        \n        if(diff === 0) // window cannot be increased\n            return ans3;\n        else\n            return addMod(ans1,mulMod(subMod(k,1), diff)); // window is increased with each k (a+(n-1)*d)\n    }\n};\n```\nThe code and explanation is large but this might help in case when you are not able to come with a short solution in one go.\n\nTime Complexity:\nO(3*n) (k=3) = O(n) \n\nSpace Complexity:\nO(3*n) (k=3) = O(n)\n\n\n\n\n\n\n
['JavaScript']