数组

输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)

package shuzu;
public class sss {

    public static void main(String[] args) {
        int[] arr={1,-2,3,10,-4,7,2,-5};
        System.out.println(findGreatestSum(arr));
    }
    
    public static int findGreatestSum(int[] arr){
        //定义最大子数组的和为greateSum
        int greateSum=0;
        //定义子数组的和为geneSum
        int geneSum=0;
        for (int i = 0; i < arr.length; i++) {
            if(geneSum<0){
                geneSum=arr[i];
            }else {
                geneSum+=arr[i];
            }
            if(geneSum>greateSum)
                greateSum=geneSum;
        }
        return greateSum;
    }
    
}

设计思想

将数组从第一个元素遍历求和 当元素之和小于0时归零，并继续遍历，其最后和为最大子数组的和。

运行结果