Understanding Kadane's Algorithm Implementation and Integer Limits in C++

I'm working on implementing Kadane's Algorithm to find the subarray with the maximum sum. I have some questions about the implementation and the use of integer limits:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int currsum[n+1];
    currsum[0] = 0;
    for (int i = 1; i <= n; i++) {
        currsum[i] = currsum[i-1] + arr[i-1];
    }
    int MaxSum = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 0; j < i; j++) {
            sum = currsum[i] - currsum[j];
            MaxSum = max(sum, MaxSum);
        }
    }
    return 0; 
}

1. Array Indexing: Why is currsum defined as currsum[n+1] instead of currsum[n]? What's the reasoning behind this off-by-one indexing?

2. Prefix Sum Calculation: In the line currsum[i] = currsum[i-1] + arr[i-1];, why are we using arr[i-1] instead of arr[i]? How does this relate to the size of currsum?

3. Integer Limits: Why do we initialize MaxSum with INT_MIN when we're looking for a maximum value? Conversely, why might we use INT_MAX when initializing variables for finding minimum values?

4. Algorithm Efficiency: This implementation seems to have a time complexity of O(n²). Is there a more efficient way to implement Kadane's Algorithm?

5. Use of <bits/stdc++.h>: I've seen this header used in competitive programming. What are the pros and cons of using it in practice?

Any insights into these aspects of the implementation would be greatly appreciated. Thank you!

1. Have you heard of prefix sums? (aka running totals, cumulative sums, scans). N+1 is used because prefix sums also needs to include an empty subarray.
2. You use INT_MIN for maximum because the max() function takes the larger of the two values, so MaxSum is always increasing. If you make MaxSum = 0 at the beginning, or some other number, there is a chance that 0 is larger than any of the actual sums. To make sure that the default value does not override the actual values, you set it to as low as possible.