Using Kadane Explained in Hindi
🔥 What is Kadane's Algorithm?
Agar Kadane's Algorithm nahi pata? No tension! Check this out: Kadane's Algorithm Explained 🚀
🚀 Approach✅ Step 1: Pehle original a
🔥 **What is Kadane's Algorithm?**
----------------------------------

*   **Agar Kadane's Algorithm nahi pata?** No tension! Check this out: [Kadane's Algorithm Explained 🚀](https://leetcode.com/problems/maximum-subarray/solutions/6148473/all-about-kadanes-algorithm-by-sapilol-wzdx/)

* * *

# 🚀 **Approach**

✅ **Step 1:** Pehle **original array pe Kadane's Algorithm** lagao aur maximum sum store kar lo.

✅ **Step 2:** Ek **new array banao jo original ka `2x` version ho** (concatenation kar ke). Fir ispe bhi Kadane lagao.

✅ **Step 3:**  
🔹 Agar **total sum > 0** ho, toh `(k-2) * totalSum` add kar do kyunki `k` baar concatenate karna hai.  
🔹 Agar **total sum ≤ 0**, toh **sirf Kadane(2x array)** ka result return karo.

💡 **Why (k-2) times?** Kyunki pehle `2x` array pe Kadane laga chuke hain, baaki `k-2` copies ka sum directly add ho sakta hai.

* * *
# 📌 **Complexity**

✅ **Time Complexity:** `O(n)` (fastest possible)  
✅ **Space Complexity:** `O(1)` (no extra space)

---

✅ **Code (Optimized Kadane's Algorithm)**
-----------------------------------------

```cpp
class Solution {
public:
    const int mod = 1e9 + 7;

    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long sum = 0, maxi = 0;

        // 🔹 Step 1: Kadane's algorithm on single array
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            maxi = max(maxi, sum);
            if (sum < 0) sum = 0;
        }

        if (k == 1) return maxi % mod;

        // 🔹 Step 2: Kadane's on two copies of the array
        long long totalSum = accumulate(arr.begin(), arr.end(), 0LL);
        sum = 0;
        long long kadane2 = 0;

        for (int i = 0; i < 2 * arr.size(); i++) {
            sum += arr[i % arr.size()];
            kadane2 = max(kadane2, sum);
            if (sum < 0) sum = 0;
        }

        // 🔹 Step 3: If total sum is positive, use formula
        if (totalSum > 0)
            return (kadane2 + (k - 2) * totalSum % mod) % mod;

        return kadane2 % mod;
    }
};
```

* * *


['C++']