C++ || DP || Kadane Algo || Easy with Explanation
In this question, we can solve it by using Kadane Algorithm : \n\n1.for the idea of kadane algorithm, it helps us to find the longest continuous number in an ar
In this question, we can solve it by using Kadane Algorithm : \n\n1.for the idea of kadane algorithm, it helps us to find the longest continuous number in an array.\n2.for the question, we can divide it as two cases. For the case one, if k = 1, just call the kadane function to find the max value.\n3. for other cases, use accumulate function to count the sum of the the orignal array.\n4.  and then we need to insert the copy of the original array into the array. \n5.  if the sum is large than zero, we can just count result by adding (k-2)*sum % mod.\n6.  Finally, return the function call of kadane(doubled array) + result(if sum < 0, whatever the k of value is(except 2), it wont affect the answer).\n\nThat is my sharing about this question.\n\n\n```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    // use kadane algorithm to find the longest continuous number in an array.    \n    long kadane (vector<int>& arr){\n        int maxEndingHere = 0;\n        int maxAll = 0;\n        int size = arr.size();\n        for(int i=0; i<size; i++){\n            maxEndingHere += arr[i]%mod;\n            // if the maxEndingHere is smaller than 0, we just reset it.\n            if(maxEndingHere < 0) maxEndingHere = 0;\n            maxAll = max(maxEndingHere, maxAll);\n        }\n        return maxAll;\n    }\n    \n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        if(arr.size() == 0) return 0;\n        int size = arr.size();\n        // case one, k == 1, just input the result.\n        if(k==1) return kadane(arr)%mod;\n        \n\t\t// since we want to check whether the actual sum of the array is larger than 0\n        long long sum = accumulate(arr.begin(), arr.end(), 0) % mod; \n\t\t\n        // for other cases, we insert the copy of the array into the array.\n        for(int i=0; i<size; i++){\n            arr.push_back(arr[i]);\n        }\n\n        \n        int result = 0;\n        // sum of original array is larger than 0, we dont need to call the kadane function\n        // k - 2 is because we haved doubled the size of the original array by its copy\n        if(sum > 0){\n            result += (k-2)*sum % mod;\n        }\n\n        return (kadane(arr) + result) % mod;\n        \n    }\n};\n```
[]