时间戳

首页 > 解决方案 > 计算最长连败的总损失

java - 计算最长连败的总损失

问题描述

一个连续的数字序列，其中每个数字小于等于前一个数字，称为连败。连胜的最后一个数字和第一个数字之间的价值差异称为损失。

例如，如果在标准输出中提供了这些数字：

3, 6, 36, 32, 32, 121, 66, 24, 22, 371, 661, 6, 4, 8.

序列中最长的连续是36,32,32and121,66,24,22和661,6,4，相应的损失是 4 和 99 和 657。在这种情况下，具有 4 个数字的 2nd Streak 是最长的。所以程序应该将输出打印为 99。

我尝试使用以下程序但无法正确处理：

public class LoosingStreak {

    public static void main(String[] args) {
        int arr [] = {3, 6, 36, 32, 32, 121, 66, 24, 22, 371, 661, 6, 4, 8, -1};
        int temp [] = new int[arr.length];
        processArray(arr);
    }

    static int processArray(int [] arr) {
        int temp [] = new int[arr.length];
        int len = arr.length;
        for(int i=0; i<len-1; i++) {
            if(arr[i+1] <= arr[i]) {
                temp[i] = arr[i];
                System.out.println(temp[i]);
            }

        }

        return -1;
    }

}

输出是：36, 32, 121, 66, 24, 661, 6, 8这是不正确的。我该如何解决这个问题？

标签： java

解决方案

您需要跟踪当前最长的条纹，以及此长度条纹的当前最大损失。如果你发现一个比最大值更长的连续，更新最长的连续和最大损失。如果您发现一条与当前最长的长度相同的条纹，则更新最大损失（如果它更大）。

static int processArray(int [] arr) 
{
    int longestStreak = 0;
    int maxLoss = 0;
    for(int j=0, i=1; i<=arr.length; i++)
    {
        if(i == arr.length || arr[i] > arr[i-1])
        {
            int streak = i - j;
            if(streak > 1 && streak >= longestStreak)
            {
                int loss = arr[j] - arr[i-1];
                if(streak > longestStreak)
                {
                    longestStreak = i-j;                
                    maxLoss = loss;
                }
                else if (loss > maxLoss)
                    maxLoss = loss;                 
            }
            j = i;
        }
    }
    return longestStreak > 0 ? maxLoss : -1;
}

请注意，我的连续数字由小于或等于前一个数字的连续数字组成，因此单例不会是连续数字。

测试：

int test[][] = {{1},
                {1, 1},
                {1, 2, 3},
                {3, 2, 1},
                {3, 2, 1, 4, 2, 1},
                {3, 6, 36, 32, 32, 121, 66, 24, 22, 371, 661, 6, 4, 8, -1}};

for(int[] arr : test)
    System.out.format("%s : %d%n", Arrays.toString(arr), processArray(arr));

输出：

[1] : -1
[1, 1] : 0
[1, 2, 3] : -1
[3, 2, 1] : 2
[3, 2, 1, 4, 2, 1] : 3
[3, 6, 36, 32, 32, 121, 66, 24, 22, 371, 661, 6, 4, 8, -1] : 99

推荐阅读