输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多

[问答题]

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，那么该数组中连续的最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

查看答案及解析

张云超

注意题目描述，有正数有负数，如果允许无非负数，那么需要单独考虑。

原理：如果前几个数加和小于零，那么前面的数所做的全是无用功所以清零

    int maxSubSum(int[] a) {
        int len = a.length;
        int sum = 0;
        int maxSum = 0;
       for(int i=0; i<len; i++) {
            sum += a[i];
            if(sum > 0){
                if(sum > maxSum) {                     maxSum = sum;                 }    
            }    
            else {
                sum = 0;
            }    
        }
        return maxSum;
    }

发表于 2019-05-30 15:05:29 回复(4)

不比较快乐喵

动态规划

import java.util.Scanner;

public class test18 {
    public static void main(String[] args) {
        int[] a = { 1, -2, 3, 10, -4, 7, 2, -5 };
        int len = a.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + a[i], dp[i]);
            res = Math.max(dp[i], res);
        }
        System.out.println(res);
    }

}

发表于 2022-07-23 10:23:47 回复(1)

brilliantspark

public static void main(String[] args) {

        int[] s ={1, -2, 3, 10, -4, 7, 2, -5};
int l = s.length;
        int[] sums = new int[l];
        sums[0] = s[0];
        int max = sums[0];
        for (int i = 1; i < l; i++) {
            sums[i] = Math.max(s[i], sums[i - 1] + s[i]);
            max = Math.max(max, sums[i]);
        }

        System.out.println(max);

    }

发表于 2019-08-13 10:29:57 回复(0)

敢闯草

public int getmax(int[] array) {
        int sum=0;
        int summax=0;

            for(int i=0;i<array.length;i++) {
                 if(sum<=0) {
                     sum=array[i];
                 }
                 else {
                     sum=array[i]+sum;
                 }
                 if(sum>summax) {
                     summax=sum;
                 }

            }


        return summax;

    }

发表于 2019-07-20 11:00:51 回复(0)

undefined_18

public class Test4 {

    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;
    }

}

发表于 2019-06-10 10:06:00 回复(0)

提交观点

问题信息

2018 用友 Java工程师

来自：用友2018秋招Jav...

上传者：小小

难度：

5条回答 28收藏 5456浏览

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多

问题信息

热门推荐

相关试题