/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	   int[] arr={-2,1,-3,4,-1,2,1,-5,4};
 
		System.out.println(maxSubArray(arr));
	}
 
    static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
 
         int n = nums.length;
        for(int i=0;i<n;i++){
             int sum = 0;
            for(int j=i;j<n;j++){
              sum = sum + nums[j];
 
              max = Math.max(max,sum);
            }
        }
 
        return max;
    }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJICAgaW50W10gYXJyPXstMiwxLC0zLDQsLTEsMiwxLC01LDR9OwoJCgkJU3lzdGVtLm91dC5wcmludGxuKG1heFN1YkFycmF5KGFycikpOwoJfQoJCiAgICBzdGF0aWMgaW50IG1heFN1YkFycmF5KGludFtdIG51bXMpIHsKICAgICAgICBpbnQgbWF4ID0gSW50ZWdlci5NSU5fVkFMVUU7CiAgICAgICAgIAogICAgICAgICBpbnQgbiA9IG51bXMubGVuZ3RoOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgICAgICAgaW50IHN1bSA9IDA7CiAgICAgICAgICAgIGZvcihpbnQgaj1pO2o8bjtqKyspewogICAgICAgICAgICAgIHN1bSA9IHN1bSArIG51bXNbal07CgogICAgICAgICAgICAgIG1heCA9IE1hdGgubWF4KG1heCxzdW0pOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gbWF4OwogICAgfQp9