C++ || Kadanes || Prefix
```\n/\n\n there will be only 3 cases possible to get max sum if we concatenate k arrays\nCase1: [......(max sum subarray= total1)......] , Its a case when our 
```\n/*\n\n there will be only 3 cases possible to get max sum if we concatenate k arrays\nCase1: [......(max sum subarray= total1)......] , Its a case when our answer comes from 1st array only after concatenation of k such arrays\nCase2: [.....................(max suffix sum=mx2)] [ (max prefix sum=mx1).................] , total2= mx2+mx1 , Its a case when our answer comes from starting two arrays only,\nCase3: [..........(max suffix sum=mx2)] [........][........][..........][........][............][.........][..........]..........(k-2)times [(max prefix sum = mx2)................] , \ntotal3= mx2+ (k-2)*sum + mx1 , \nIts a case when our answer comes from all k arrays \nOR total3= [ max suffix sum from 1st array + sum of all (k-2) middle arrays+ max prefixsum from last array ]\nAns= max(all three cases)\n\n*/\n\nint mod=1e9+7;\n\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        \n        int n=arr.size();\n        \n        vector<int>pref(n),suff(n);\n    \n        pref[0]=arr[0];\n        int mx1=pref[0];\n        \n        for(int i=1;i<n;i++){\n            pref[i]=pref[i-1]+arr[i];\n            mx1=max(mx1,pref[i]);\n        }\n        \n        suff[n-1]=arr[n-1];\n        \n        int mx2=suff[n-1];\n        \n        for(int i=n-2;i>=0;i--){\n            suff[i]=suff[i+1]+arr[i];\n            mx2=max(mx2,suff[i]);\n        }\n        \n        int sum=pref[n-1];\n        \n        int total1=kadans(arr);  // considering only one array\n        \n        if(k==1)\n            return total1;\n        \n        int total2=mx1+mx2; // considering only 2 array\n        \n       \n        int total3=mx1+mx2+1ll*sum*(k-2)%mod; // taking all arrays\n\n        \n        return max({total1,total2,total3})%mod;\n        \n    }\n    \n    int kadans(vector<int>&arr){\n        \n        int temp=0;\n        \n        int mxsum=INT_MIN;\n        \n        for(int x:arr){\n            temp=max(x,temp+x);\n            mxsum=max(mxsum,temp);\n            if(mxsum<0)\n                mxsum=0;\n        }\n        \n        return mxsum;\n        \n    }\n};\n
[]