package com.cpucode.java.simple;

/**
 * 题目描述
 * 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
 * 示例1
 * 输入
 * [1,-2,3,10,-4,7,2,-5]
 * 返回值
 * 18
 * 说明
 * 输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。
 *
 * @author : cpucode
 * @Date : 2021/1/21
 * @Time : 12:08
 * @Github : https://github.com/CPU-Code
 * @CSDN : https://blog.csdn.net/qq_44226094
 */
public class Jz30 {
    public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {

            int num = array[0];

            for(int i = 1; i < array.length; i++){
                //累加 跳过小于负值
                array[i] += array[i - 1] > 0 ? array[i -1] : 0;

                //比较累加值 和最大值
                num = Math.max(array[i], num);
            }

            return num;
        }
    }
}