的最大的一笔非递减顺序 [英] Largest sum of non-decreasing up sequence

问题描述

如。 -3,6,11,13,5，-11,4,7,8最大的一笔= 30（6,11,13原因加入-3将使之更小）

如。 7,0，-3最大的一笔= 7

如4，-1,45最大的一笔= 45

例如-3 - ， - 2，-6,0最大的一笔= 0

需要一些建议对我的code，仍马车

  INT maxSum = Integer.MIN_VALUE的;
    INT总和= 0;
    INT checkNeg = Integer.MIN_VALUE的;    的for（int i = 0; I＆LT;则为a.length;我++）{
        如果（一个[Ⅰ]≥checkNeg）{
            checkNeg =一个由[i];
        }
    }    如果（checkNeg＆下; = 0）{
        maxSum = checkNeg;
    }    如果（checkNeg大于0）{
        的for（int i = 0; I＆LT;则为a.length;我++）{
            如果（一个由[i]！= 0）{
                总和+ = a [i];
                如果（总和＆GT; maxSum）{
                    如果（ⅰ！= 0）{
                        如果（一个[Ⅰ]≥=一个[I  -  1]）{
                            maxSum =总和;
                        }其他{
                            总和=一个由[i];
                        }
                    }其他{
                        maxSum =总和;
                    }
                }
                如果（总和℃，）{
                    总和= 0;
                }
            }其他{
                总和= 0;
            }
        }
    }
    返回maxSum;
 

解决方案

试试这个

  INT maxSum = Int32.MinValue;
        INT总和= 0;            的for（int i = 0; I＆LT;则为a.length;我++）
            {
                如果（一个[Ⅰ]≥= 0）
                {
                    总和+ = a [i];
                    maxSum = Math.Max​​（总和，maxSum）;                    如果（第（i + 1＆下;则为a.length）及及（一个第[i + 1];一个由[i]））
                        总和= 0;
                }
                其他
                {
                    maxSum = Math.Max​​（一个由[i]，maxSum）;
                    总和= 0;
                }
            }        返回maxSum;
 

似乎所有的例子和其他几个工作。

有不需要'checkNeg'，此检查应该算法出一点更自然

eg. -3,6,11,13,5,-11,4,7,8 largest sum =30 (6,11,13 cause adding -3 will make the sum smaller)

eg. 7,0,-3 largest sum = 7

eg 4,-1,45 largest sum = 45

eg -3-,-2,-6,0 largest sum =0

Need some advise for my code, still buggy

    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    int checkNeg = Integer.MIN_VALUE;

    for (int i = 0; i < a.length; i++) {
        if (a[i] > checkNeg) {
            checkNeg = a[i];
        }
    }

    if (checkNeg <= 0) {
        maxSum = checkNeg;
    }

    if (checkNeg > 0) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                sum += a[i];
                if (sum > maxSum) {
                    if (i != 0) {
                        if (a[i] >= a[i - 1]) {
                            maxSum = sum;
                        } else {
                            sum = a[i];
                        }
                    } else {
                        maxSum = sum;
                    }
                }
                if (sum < 0) {
                    sum = 0;
                }
            } else {
                sum = 0;
            }
        }
    }
    return maxSum;

解决方案

Try this

        int maxSum = Int32.MinValue;
        int sum = 0;

            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] >= 0)
                {
                    sum += a[i];
                    maxSum = Math.Max(sum, maxSum);

                    if ((i+1<a.Length) && (a[i+1] < a[i]))
                        sum = 0;
                }
                else
                {
                    maxSum = Math.Max(a[i], maxSum);
                    sum = 0;
                }
            }

        return maxSum;

seemed to work for all your examples and a couple of others.

There is no need for 'checkNeg', this check should come out of the algorithm a little more naturally

这篇关于的最大的一笔非递减顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！