hackerrank新年混沌代码优化

我正在尝试优化我的解决方案Hackerranks 的“新年混乱”问题 https://www.hackerrank.com/challenges/new-year-chaos/problem。问题的要点是这样的

有一个由 n 个人组成的队列，标记为 1 到 n，每个人都可以贿赂直接在他们前面的人以交换位置并靠近队列的前面（在本例中为列表/数组的索引 0）。每个人最多只能贿赂两次（并且不能贿赂已经贿赂过自己的人）

在所有贿赂发生后，您会收到人民的命令，您的工作是确定发生了多少次贿赂才达到这一点。例如，如果给您 [3, 2, 1]，那么答案将是 3 次贿赂（人员 3 贿赂人员 1, 2，人员 2 贿赂人员 1）。

我的解决方案是，对于每个 I 人，计算 I 左侧标签大于 I 的人数（他们必须贿赂 I 人才能到达他们的左侧）。让事情变得复杂一点（稍微），给出的一些测试用例只有在有人贿赂超过 2 次的情况下才可能出现（即 [4, 1, 2, 3] - 第 4 个人贿赂第 3 个人，然后是 2 个人，然后是 1 个人）前方）。如果是这种情况，只需输出“Too Chaotic”

无论如何，这是代码：

# n is the number of people in the list
# q is the order of the people after the bribery has taken place ex. [1, 3, 2, 5, 4]

for I in range(1, n + 1): # for each person I in the list
    index = q.index(I)
    if I - index > 3: # more than two bribes
        bribes = "Too chaotic"
        break
    for j in range(index): # for each number to the left of I, if greater than I, count it as a bribe
        if q[j] > I: 
            bribes = bribes + 1
print bribes

我的问题是，代码在一些较大的测试用例中超时（每个测试用例的运行时间只有这么多）。如何优化算法使其不会超时？我应该用另一种语言尝试这个问题吗？

对您的解决方案的一种优化是从 q[i] - 2 而不是 0 开始嵌套循环。由于没有人可以向前跳转到其原始位置超过 2，因此任何高于 q[i] 的值都只能是直到索引 q[i] -2。

就像是：

for(int j = Math.max(0, q[i] - 2); j < i; j++) {
    if(q[j] > q[i]) {
      bribe++;
    }
}