#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int maxSubArray(vector<int>& nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];
 
    for (int i = 1; i < nums.size(); i++) {
        // Either extend current subarray or start new one
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
 
    return maxSum;
}
 
// To also find the subarray itself:
pair<int, pair<int,int>> maxSubArrayWithIndices(vector<int>& nums) {
    int currentSum = nums[0], maxSum = nums[0];
    int start = 0, end = 0, tempStart = 0;
 
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > currentSum + nums[i]) {
            currentSum = nums[i];
            tempStart = i;
        } else {
            currentSum += nums[i];
        }
 
        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
    }
 
    return {maxSum, {start, end}};
}
 
int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Max subarray sum: " << maxSubArray(nums) << endl;  // 6
 
    auto result = maxSubArrayWithIndices(nums);
    cout << "Sum: " << result.first
         << " from index " << result.second.first
         << " to " << result.second.second << endl;
    // Sum: 6 from index 3 to 6 -> [4, -1, 2, 1]
    return 0;
}

def max_sub_array(nums):
    """Kadane's Algorithm -- find max subarray sum."""
    current_sum = max_sum = nums[0]
 
    for num in nums[1:]:
        # Key decision: extend or start fresh?
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
def max_sub_array_with_indices(nums):
    """Also returns the start and end indices of the max subarray."""
    current_sum = max_sum = nums[0]
    start = end = temp_start = 0
 
    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]
 
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
 
    return max_sum, start, end
 
# Examples
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_sub_array(nums))  # 6
 
total, s, e = max_sub_array_with_indices(nums)
print(f"Sum: {total}, subarray: {nums[s:e+1]}")
# Sum: 6, subarray: [4, -1, 2, 1]