print maximum sum subarray

To print the maximum sum subarray in C++, you can follow these steps:

1. Initialize variables: Start by initializing three variables: maxSoFar, maxEndingHere, and start. Set maxSoFar and maxEndingHere to 0, and start to 0. These variables will keep track of the maximum sum found so far, the maximum sum ending at the current position, and the starting index of the maximum sum subarray.

int maxSoFar = 0;
int maxEndingHere = 0;
int start = 0;

1. Iterate through the array: Use a loop to iterate through the given array. Start the loop from index 0 and continue until the end of the array.

for (int i = 0; i < n; i++) {
    // ...
}

1. Update maxEndingHere: Inside the loop, update maxEndingHere by adding the current element to it. If maxEndingHere becomes negative, reset it to 0.

maxEndingHere = maxEndingHere + arr[i];
if (maxEndingHere < 0) {
    maxEndingHere = 0;
}

1. Update maxSoFar and start: After updating maxEndingHere, check if it is greater than maxSoFar. If it is, update maxSoFar and start accordingly.

if (maxEndingHere > maxSoFar) {
    maxSoFar = maxEndingHere;
    start = i;
}

1. Print the subarray: After the loop ends, you can print the subarray with the maximum sum. Iterate from start to i (which represents the end of the subarray) and print the elements.

for (int j = start; j <= i; j++) {
    cout << arr[j] << " ";
}

Putting it all together, here's the complete code:

#include <iostream>
using namespace std;

void printMaxSubarray(int arr[], int n) {
    int maxSoFar = 0;
    int maxEndingHere = 0;
    int start = 0;

    for (int i = 0; i < n; i++) {
        maxEndingHere = maxEndingHere + arr[i];
        if (maxEndingHere < 0) {
            maxEndingHere = 0;
        }
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            start = i;
        }
    }

    for (int j = start; j <= i; j++) {
        cout << arr[j] << " ";
    }
}

int main() {
    int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printMaxSubarray(arr, n);

    return 0;
}

This code will find and print the subarray with the maximum sum.