[C++] Simple Kadane Algorithm with Explanation
Kadane Algo - Complexity O(size of array) But maxm size array we can make is of order 10^7\nSo according to constraints, we cannot duplicate the array k times a
Kadane Algo - Complexity O(size of array) But maxm size array we can make is of order 10^7\nSo according to constraints, we cannot duplicate the array k times and apply Kadane\nSay arr = [1,-2,1], k = 5 \nApproach-\n1. Duplicate the given array. \n-- So duplicated array will be [1 -2 1 1 -2 1]\n\n2. Apply Kadane on the duplicated array. Here it will give maxm subarray sum as 2(1 from first half+ 1 from sec half)\n--The maximum subarray sum can be constituted with elements from two possible ways\n---Way 1:From first two duplicates [1 -2 1][1 -2 1]..(k-2) duplicates\n---Way 2: From all the duplicates. [1 -2 1]...(k-2) duplicates..[1 -2 -1]\n\n3. Find sum of all elements of given array. Here sum = 1-2+1=0\n4. if sum>0 then result= Result of step 2 + (k-2) * sum          (Way 2 of step 2)\n-- else result=sum                                                                   (Way 1 of step 2)\n---So here result=2                            \n\nclass Solution {\npublic:\n\n    long long int kadane(vector<int>& a)\n    {\n        long long int cs=0;long long int ms=0;\n        for(int i=0;i<a.size();i++)\n        {\n            cs+=a[i];\n            ms=max(ms,cs);\n            if(cs<0) cs=0;\n        }\n        return ms;\n    }\n    \n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n     int mod=1000000007;\n     if(k==1) return kadane(arr)%mod;\n     int n=arr.size();\n     vector<int>a(n*2);\n     long long int sum=0;\n     //Duplicating array and finding sum of array\n     for(int i=0;i<n;i++) {a[i]=arr[i];sum+=arr[i];}\n     for(int i=n;i<2*n;i++) a[i]=arr[i-n];\n     \n     long long int res=kadane(a)%mod;\n     if(sum>0) return res+((k-2)*sum)%mod;\n     return res;\n    }\n    };
[]