Simple Kadane's Algo Modification || Easy to Understand ✅✅ || C++
Intuition\nModified Kadane\'s Algorithm\n\n# Approach\nif(k==1) use Kadane\'s Algo\nif(sum of array is positive) return (k-2)*(totalsum)+(kadane\'s of first two
# Intuition\nModified Kadane\'s Algorithm\n\n# Approach\nif(k==1) use Kadane\'s Algo\nif(sum of array is positive) return (k-2)*(totalsum)+(kadane\'s of first two copies of original array)\nif(sum of array is negative ) return kadane\'s of first two copies of original array.\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(2n)\n\n# Code\n```\n# define ll long long\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        ll mod= 1000000007;\n        if(k==1)\n        {\n            ll ans=0,sum=0;\n            for(int i=0;i<arr.size();i++)\n            {\n                sum+=arr[i];\n                sum%=mod;\n                if(sum<0)\n                {\n                    ans=max(sum,ans);\n                    sum=0;\n                }\n                ans=max(ans%mod,sum%mod);\n                ans%=mod;\n            }\n            return ans % mod;\n        }\n        ll total=0;\n        for(auto &i:arr)\n        {\n            total+=i;\n            total%=mod;\n        }\n        total%=mod;\n            vector<int>newarr=arr;\n            int cnt=2;\n            newarr.insert(newarr.end(),arr.begin(),arr.end());\n            ll ans=0,sum=0;\n            for(int i=0;i<newarr.size();i++)\n            {\n                sum+=newarr[i];\n                ans=max(sum,ans);\n                if(sum<0) sum=0;\n            }\n            ans%=mod;\n            ll res= ans+(k-2)*total;\n            return (total<0) ? ans%mod : res%mod;\n        \n        \n            \n\n    }\n};\n```
['C++']