//faster & more efficent code
#include <iostream>
using namespace std;
int main() {
	cout << "Interval with Greatest Sum inside a Sequence of n Integers:" << endl << endl;
	int n;
	cout << "n = ";
	cin >> n;
	int A[n];
	for (int i=0; i<n; i++){
		cout << "a" << i+1 << " = ";
		cin >> A[i];
	}
	int start = -1, end = -1, maxSum = INT_MIN;
	int intervalSum = 0, intervalStart = 0;
	for (int i=0; i<n; i++) {
		if (intervalSum < 0) {
			intervalSum = A[i];
			intervalStart = i;
		} else {
			intervalSum += A[i];
		}
		if (intervalSum > maxSum) {
			maxSum = intervalSum;
			start = intervalStart;
			end = i;
		}
	}
	cout << endl << "Sequence: ";
	for (int i=0; i<n; i++){
		cout << A[i] << " ";
	}
	cout << endl << endl;
	cout << "Interval with Greatest Sum: "; 
	for (int i=start; i<end+1; i++){
		cout << A[i] << " ";
	}
	cout << endl << endl << "Press Enter to exit. ";
	cin.get();
	cin.get();
	return 0;
}