Untitled

#include <iostream>
#include <vector>

// Function to find the maximum sum subarray using a naive approach
void findMaxSubarray(const std::vector<int>& arr)
{
    int n = arr.size();
    int maxSum = 0; // Initialize maximum sum
    int start = 0; // Initialize starting index of subarray
    int end = -1; // Initialize ending index of subarray
    
    // Find maximum sum subarray
    for (int i = 0; i < n; ++i)
    {
        int currentSum = 0;
        for (int j = i; j < n; ++j)
        {
            currentSum += arr[j];
            
            // Update maximum sum and subarray indices if current sum is greater
            if (currentSum > maxSum)
            {
                maxSum = currentSum;
                start = i;
                end = j;
            }
        }
    }
    
    // Print the maximum sum subarray
    std::cout << "Maximum Sum Subarray: ";
    for (int i = start; i <= end; ++i)
        std::cout << arr[i] << " ";
    
    std::cout << std::endl;
    std::cout << "Starting Index: " << start << std::endl;
    std::cout << "Ending Index: " << end << std::endl;
    std::cout << "Sum: " << maxSum << std::endl;
}

int main()
{
    // Input array
    std::vector<int> arr = {13, -3, -25, 20, -3, 16, -23, 18, 20, -7, 12, -5, 22, 15, -4, 7};
    
    // Find the maximum sum subarray
    findMaxSubarray(arr);
    
    return 0;
}