Simple logic  with explanation ✅
Approach\n- First we compute the \n    - (best here )max subarray sum possible of single array given \n    - suffix sum max \n    - prefix sum max\n    - and to
# Approach\n- First we compute the \n    - (best here )max subarray sum possible of single array given \n    - suffix sum max \n    - prefix sum max\n    - and total sum of the array \n- now after computing we see that our merge array \'s above 4 things will be \n    - there are 3 cases 1. a\'s max subarray sum is best , 2. b\'s is max , 3. half from a and half from b \n        - ans.best = max({a.best, b.best, (a.suffBest + b.prefBest)});\n\t\n    - for prefix sum max we have 2 cases 1. a\'s is maximum , 2. we need to include whole a and then take prefix of b\n\t    - ans.prefBest = max(a.prefBest , (a.tot + b.prefBest));\n\t- Similar in the case of suffix \n\t     - ans.suffBest = max(b.suffBest , (b.tot + a.suffBest));\n\t- total will be the sum of both arrays ans.tot = a.tot + b.tot;\n\n\n\n- first merge two arrays then the merged array with ith array \n\n![Screenshot 2023-10-20 at 5.32.07\u202FPM.png](https://assets.leetcode.com/users/images/2a4b58fa-ac82-4c9b-9873-70767dbdf806_1697803714.7277424.png)\n\n# Complexity\n- Time complexity:\n    O(n)\n\n# Code\n```\n#define all(var)                      var.begin(), var.end()\nint mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}\nconst int mod = 1e9 + 7;\n#define ll long long \nclass Solution {\npublic:\n\tint n ;\n\tstruct concatKarr {\n\t\tll best  , suffBest  , prefBest, sum  , tot ;\n\t\tvoid build(vector<int> arr) {\n\t\t\tint n = arr.size();\n\n            // total sum of array \n\t\t\ttot = accumulate(all(arr), 0ll);\n\n            // prefix best \n\t\t\tprefBest = arr[0] , sum = arr[0];\n\t\t\tfor (int i = 1 ; i < n ; i++) {\n\t\t\t\tsum += arr[i];\n\t\t\t\tprefBest = max(prefBest, sum );\n\t\t\t}\n\n            // suffix best \n\t\t\tsuffBest = arr[n - 1] , sum = arr[n - 1];\n\t\t\tfor (int i = n - 2 ; i >= 0 ; i--) {\n\t\t\t\tsum += arr[i];\n\t\t\t\tsuffBest = max(suffBest, sum );\n\t\t\t}\n\n            // by using kandane we find the max subarray sum \n\t\t\tbest = arr[0] , sum = arr[0];\n\t\t\tfor (int i = 1 ; i < n ; i++) {\n\t\t\t\tsum += arr[i];\n\t\t\t\tbest = max(best, sum );\n\t\t\t\tif (sum < 0 ) sum = 0;\n\t\t\t}\n\n\t\t}\n\t};\n\n\tconcatKarr merge(concatKarr a , concatKarr b) {\n\t\tconcatKarr ans ;\n\n        //merge logic explained above \n\t\tans.best = max({a.best, b.best, (a.suffBest + b.prefBest)});\n\t\tans.prefBest = max(a.prefBest , (a.tot + b.prefBest));\n\t\tans.suffBest = max(b.suffBest , (b.tot + a.suffBest));\n\t\tans.tot = a.tot + b.tot;\n\n\t\treturn ans;\n\t}\n\tint kConcatenationMaxSum(vector<int>& arr, int k) {\n\t\tn = arr.size();\n\t\tconcatKarr bb ;\n\t\tbb.build(arr);\n\n\t\tconcatKarr ans = bb;\n\t\tfor (int i = 1 ; i < k ; i++) {\n\t\t\tans = merge(ans , bb);\n\t\t}\n\n\t\treturn max(ans.best , 0ll)%mod;\n\t}\n\n};\n\n```
['Array', 'Dynamic Programming', 'Python', 'C++', 'Java']