#include <iostream>
using namespace std;
#include<bits/stdc++.h>
 
int main() {
	// your code goes here
	int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
	int n = sizeof(arr)/sizeof(int);
	//there are i+1 subarrays ending at i we have to find the maximum subarray sum ending at i 
	vector<int>p1;
	for(int i = 0 ; i <n ; i++){
		int sum = 0; int t=INT_MIN;
		for(int j = i ;j>=0;j--){
			sum+=arr[j];
			t=max(t,sum);
		}
		p1.push_back(t);
	}
	for(int i = 0 ; i<n;i++) cout<<p1[i]<<" ";
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgYXJyW10gPSB7LTIsMSwtMyw0LC0xLDIsMSwtNSw0fTsKCWludCBuID0gc2l6ZW9mKGFycikvc2l6ZW9mKGludCk7CgkvL3RoZXJlIGFyZSBpKzEgc3ViYXJyYXlzIGVuZGluZyBhdCBpIHdlIGhhdmUgdG8gZmluZCB0aGUgbWF4aW11bSBzdWJhcnJheSBzdW0gZW5kaW5nIGF0IGkgCgl2ZWN0b3I8aW50PnAxOwoJZm9yKGludCBpID0gMCA7IGkgPG4gOyBpKyspewoJCWludCBzdW0gPSAwOyBpbnQgdD1JTlRfTUlOOwoJCWZvcihpbnQgaiA9IGkgO2o+PTA7ai0tKXsKCQkJc3VtKz1hcnJbal07CgkJCXQ9bWF4KHQsc3VtKTsKCQl9CgkJcDEucHVzaF9iYWNrKHQpOwoJfQoJZm9yKGludCBpID0gMCA7IGk8bjtpKyspIGNvdXQ8PHAxW2ldPDwiICI7CgkKCXJldHVybiAwOwp9