C++||DP Kadane's Algorithm ||
\tclass Solution {\n\tpublic:\n    int kConcatenationMaxSum(vector& arr, int k) {\n        long long int sum=0;\n        int mod=(int)(1e9+7);\n        int glob
\tclass Solution {\n\tpublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        long long int sum=0;\n        int mod=(int)(1e9+7);\n        int globemax=0,n=arr.size();\n        for(int i=0;i<arr.size();++i)\n            sum=(sum+arr[i])%mod;\n        if(k==1){\n            int cmax=arr[0];\n            int gmax=arr[0];\n            for(int i=1;i<arr.size();++i){\n                cmax=max(arr[i],arr[i]+cmax);\n                gmax=max(gmax,cmax);\n            }\n            return gmax;\n        }else{\n            int finalans = arr[0];\n        int curr = arr[0];\n        for(int i = 1 ; i < 2 * n; i++){\n            curr = max(arr[i % n], arr[i % n] + curr);\n            finalans = max(finalans, curr);\n        }\n            globemax=finalans;\n        }\n        if(sum < 0) return max(0,globemax%mod);\n         int ans=(globemax+((k-2)*sum))%mod;\n            \n        return ans;\n    }
[]