Determining Slope Approach - Java
I thought of this as a line.  Store the max sum for each of the first three runs.  If then second and third run are equal, than we know that the line is flat an
I thought of this as a line.  Store the max sum for each of the first three runs.  If then second and third run are equal, than we know that the line is flat and we return the max from third run.  If they are different, we know it is linear y = mx + b.  Each kth term has a slope (m) or difference (3rd term - 2nd term).  Determine b from the 2nd term (1st term may be off, example in code).  Final formula would be the difference (m) * (k-2) + 2nd term.\n\nExample Input:\n[1,-2,3]\nMaxArray = [3, 5, 7] \nThe slope (m) is 2 and b = 3.\n\n```\npublic int kConcatenationMaxSum(int[] arr, int k) {\n\tint mod = 1000000007;\n\tint max = 0, sum = 0, j = 3;\n\tint[] maxArray = new int[3];\n\twhile (j-- > 0) {\n\t\tfor (int i = 0; i < arr.length; i++) {\n\t\t\tsum = (sum + arr[i]) % mod;\n\t\t\tif (sum > max) {\n\t\t\t\tmax = sum;\n\t\t\t}\n\t\t\tif (sum < 0) {\n\t\t\t\tsum = 0;\n\t\t\t}\n\t\t}\n\t\tmaxArray[2-j] = max;\n\t}\n    if (k < 4) return maxArray[k-1];\n\tif (maxArray[2] == maxArray[1]) {\n\t\treturn maxArray[2];\n\t} else {\n\t\tint dif = maxArray[2] - maxArray[1];\n\t\t// use 2nd term for b instead of 1st because in some cases 1st term may not produce true b value\n\t\t// Example - [10, -12, 8] k = 15\n\t\t// Max per K - 10, 14, 20, 26, 32, 38... \n\t\t// m = 6 and b = 2\n\t\treturn (int) (((long) dif * (k-2) % mod) + maxArray[1]) % mod;\n\t}\n}\n```
[]