class Solution(object):

    def maxSubArray(self, nums):

        sum = 0

        max_sub_sum = nums[0]

        for num in nums:

            sum += num

            if sum > max_sub_sum:

                max_sub_sum = sum

            if sum < 0:

                sum = 0

        return max_sub_sum

class Solution(object):

    def maxSubArray(self, nums):

        """

        :type nums: List[int]

        :rtype: int

         """

        for i in range(1, len(nums)):

            nums[i]= nums[i] + max(nums[i-1], 0)

        return max(nums)

class Solution {

    public int maxSubArray(int[] nums) {

        if (nums == null || nums.length <= 0)

            return 0;

        int len = nums.length;

        return getInfo(nums,0,len - 1).mSum;

    }

    class wtevTree{

        int lSum;

        int rSum;

        int iSum;

        int mSum;

        wtevTree(int l, int r, int i, int m){

            lSum = l;

            rSum = r;

            iSum = i;

            mSum = m;

        }

    }

    wtevTree pushUp(wtevTree leftT,wtevTree rightT){

        int l = Math.max(leftT.lSum,leftT.iSum + rightT.lSum);

        int r = Math.max(leftT.rSum + rightT.iSum,rightT.rSum);

        int i = leftT.iSum + rightT.iSum;

        int m = Math.max(leftT.rSum + rightT.lSum,Math.max(leftT.mSum,rightT.mSum));

        return new wtevTree(l,r,i,m);

    }

    wtevTree getInfo(int[] nums,int left,int right){

        if(left == right)

            return new wtevTree(nums[left],nums[left],nums[left],nums[left]);

        int mid = (left + right) >> 1;

        wtevTree leftT = getInfo(nums,left,mid);

        wtevTree rightT = getInfo(nums,mid + 1,right);

        return pushUp(leftT,rightT);

    }

}