Javascript可塑性最大切片问题

Question

I试图解决Javascript中的以下算法问题：

给出了一个由N个整数组成的阵列A。

它包含连续N天的股票的每日价格。

如果一只股票在P当天被买入，并在Q当天卖出，

在哪里0 ≤ P ≤ Q < N，

那么这种交易的利润等于A[Q] − A[P]，

前提是A[Q] ≥ A[P]。

否则，事务会带来A[P] − A[Q]的损失。

例如，考虑由以下六个元素组成的数组A：

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

如果一只股票在第0天买进，在第2天卖出，2048的损失就会发生，因为A[2] − A[0] = 21123 − 23171 = −2048。

如果在第4天买进股票，在第5天卖出，354的利润就会出现，因为A[5] − A[4] = 21367 − 21013 = 354。

最大可能的利润是356。

如果一只股票在第一天买进，在第五天卖出，就会发生这种情况。

写一个函数，

函数解(A)；

给定一个由N个整数组成的数组A，其中包含连续N天的股票日价格，则在此期间返回一笔交易可能带来的最大利润。

如果不可能获得任何利润，则函数应该返回0。

例如，给定的数组A由六个元素组成，这样：

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

函数应该返回356，如前所述。

为下列假设编写一个有效的算法：

N是范围[0..400,000]中的整数；array A的每个元素都是范围[0..200,000]中的整数。

这是我目前的解决方案，它在‘200 K值的混沌序列从100 K.120 K，然后200 K值从0..100 K’的混沌序列上失败，在那里它成功0.07秒太迟了。

function solution(A) {
    length = A.length
    if (A > 400000) return 0
    let lastStart = A[0]
    let lastMax = A[0]
    let diff = 0
    for (i=0; i < length; i++){
        if (A[i] < lastMax) lastMax = A[i]
        if (A[i] < lastStart) lastStart = A[i]
        if (A[i] > lastMax) {
            lastMax = A[i]
            if (lastMax - lastStart > diff) diff = lastMax - lastStart
        }
    }
    return diff > 0 ? diff : 0
}

这似乎是O(N)，因此应该过去，但似乎正在失败。

有人能看到是什么导致了这一切吗。

我知道有其他方法可以解决这个问题，但是我真的想知道为什么这个方法没有达到时限。

谢谢!

Answer 1

它就像这样简单(通过所有测试)：

function solution(A) {
    let min = A[0]
    let dif = 0
    for (let i = 1; i < A.length; i++) {
        if (A[i] < min)
            min = A[i]
        else if (A[i] - min > dif)
            dif = A[i] - min
    }
    return dif
}

if (A > 400000) return 0.

• Here --您可能应该将<更改为>或完全省略这一行：if (A[i] < lastMax) lastMax = A[i].

• Your逻辑似乎是错误的，只有在看到新的最大值时才会更改diff。尽管这并不重要，因为您之前重置了lastMax。

因此，您的代码似乎工作正常，只是一些小的改进。我的猜测是，如果很多人同时提交解决方案，那么需要更长时间才能通过性能测试。

Answer 2

以下是Python中基于最大切片探测算法的最快算法( O(N) )。

def solution(A):
 if(len(A)==0):
     return 0
 else:
     min_start= A[0]
     max_profit = 0
     for a in A:
         min_start = min(a, min_start)
         max_profit = max(max_profit, a - min_start)
     return max_profit

Answer 3

这是C中的简单解决方案。https://app.codility.com/demo/results/trainingVTW26A-737/

检测时间复杂度: O(N)

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)

    int i, sum, max, globalMax;

    sum = 0;
    max = globalMax = A[0];

    for (i = 1 ; i < N; ++i) 
    {
        sum = A[i] + max;
        max = (sum > A[i]) ? sum : A[i];

        if (max > globalMax) 
        {
            globalMax = max;
        }
    } 

    return globalMax;
}