C++ Solution  ✅ || Kadens Algo || 100% Faster Code  ✅ || Easy to Understand || Image Explaination
Check out the image :\n\n\n# CODE :\n\nclass Solution {\npublic:\n        \n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n                \n         
# Check out the image :\n![image](https://assets.leetcode.com/users/images/763c8f93-13e5-44d0-8cf6-f358605f8957_1688890254.255391.jpeg)\n\n# CODE :\n```\nclass Solution {\npublic:\n        \n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n                \n                int mod = 1e9 + 7;\n                int n = arr.size();\n                long long  Kadnes_ans = 0;\n                long long arr_sum = 0;\n            \n            // Using Kadnes Algo \n              long long temp = 0;\n              for(int i =0  ;i < n ;i++){\n                    temp += arr[i];\n                    if(temp < 0) temp =0;\n                    Kadnes_ans = max(Kadnes_ans,temp);\n                        }\n            // Edge Case\n            if(k == 1) return Kadnes_ans%mod;\n            \n        \n              long long bestpreffix = 0;\n              long long bestsuffix = 0;\n                temp = 0;\n            for(int i = 0 ; i < n ; i++){\n                    temp += arr[i];\n                    bestpreffix= max(bestpreffix , temp);\n                \n            }\n            \n            sum = temp; // Array Sum \n            temp = 0;\n            for(int i = n-1 ; i>= 0;i--){\n                    temp += arr[i];\n                    bestsuffix = max(bestsuffix,temp);\n                                       \n            }\n           long long ans;  \n        if(sum >= 0) { // For positive Array Sum\n        \n       ans = max(bestpreffix + bestsuffix +  (long long)(k-2)*(long long)(sum)  ,Kadnes_ans );\n                \n            }\n        else{    \n                // For Negative Array Sum\n             ans =  max((bestpreffix + bestsuffix), Kadnes_ans);\n         }\n               return ans%mod;\n                    \n            \n            \n    }\n};\n```
['Dynamic Programming', 'C']