Javascript Codility 最大切片问题

Question

我正在尝试 Codility 的 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]

范围内的整数。

这是我当前的解决方案，它在“[100K..120K] 中的 200K 值的混沌序列，然后是 [0..100K] 中的 200K 值”上的性能失败，成功晚了 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

这是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 2

就这么简单（通过所有测试）：

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

  。
• 在这里，您可能应该将

  <

  更改为

  >

  或完全省略该行：

  if (A[i] < lastMax) lastMax = A[i]

  。
• 你的逻辑似乎是错误的，只有当你看到新的最大值时，你才会改变

  diff

  。虽然没关系，因为你之前重置过

  lastMax

  。

所以你的代码似乎工作正常，只是做了一些小的改进。我的猜测是，如果很多人同时提交解决方案，那么需要更长的时间，并且您无法通过性能测试。

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

Answer 4

100% 解决方案是快速的：

public func solution(_ A : inout [Int]) -> Int {
    guard var minPrice = A.first else { return 0 }
    var maxProfit = 0

    for i in 1..<A.count {
        let dif = A[i] - minPrice

        if dif <= 0 {
            minPrice = A[i]
        } else {
            maxProfit = max(maxProfit, dif)
        }
    }

    return maxProfit
}