为什么我的for循环不起作用？（Python）

我确信我的if / elif语句可以改进，但这是我首先想到的。如有需要，我可以稍后再谈。

@ or1426的解决方案创建当前最长排序序列的列表，并将其复制到longest发现更长序列的位置。每当找到更长的序列时，都会创建一个新列表，并将其添加到每个字符的列表中。在Python中，这实际上非常快，但请参见下文。

@Deej的解决方案将当前最长的排序序列保留在字符串变量中，并且每次找到更长的子字符串（即使是当前序列的延续）时，该子字符串也会保存到列表中。该列表最终具有原始字符串的所有已排序子字符串，并且通过调用来找到最长的子字符串max。

这是一个更快的解决方案，它仅跟踪当前最大序列的索引，并且仅在找到未排序顺序的字符时才将更改最长。

def bjorn4(s):
    # we start out with s[0] being the longest sorted substring (LSS)
    longest = (0, 1)    # the slice-indices of the longest sorted substring
    longlen = 1         # the length of longest
    cur_start = 0       # the slice-indices of the *current* LSS
    cur_stop = 1

    for ch in s[1:]:       # skip the first ch since we handled it above
        end = cur_stop-1   # cur_stop is a slice index, subtract one to get the last ch in the LSS
        if ch >= s[end]:   # if ch >= then we're still in sorted order..
            cur_stop += 1  # just extend the current LSS by one
        else:
            # we found a ch that is not in sorted order
            if longlen < (cur_stop-cur_start):
                # if the current LSS is longer than longest, then..
                longest = (cur_start, cur_stop)    # store current in longest
                longlen = longest[1] - longest[0]  # precompute longlen

            # since we can't add ch to the current LSS we must create a new current around ch
            cur_start, cur_stop = cur_stop, cur_stop+1

    # if the LSS is at the end, then we'll not enter the else part above, so
    # check for it after the for loop
    if longlen < (cur_stop - cur_start):
        longest = (cur_start, cur_stop)

    return s[longest[0]:longest[1]]

快多少？它的速度几乎是orl1426的两倍，是deej的三倍。与往常一样，这取决于您的输入。存在的排序子字符串块越多，上述算法与其他算法相比将越快。例如，在长度为100000的输入字符串中，包含交替的100个随机字符和100个有序字符，我得到：

bjorn4: 2.4350001812
or1426: 3.84699988365
deej  : 7.13800001144

如果我将其更改为交替使用1000个随机字符和1000个排序的字符，那么我得到：

bjorn4: 23.129999876
or1426: 38.8380000591
deej  : MemoryError

更新：这是我的算法的进一步优化版本，带有比较代码：

import random, string
from itertools import izip_longest
import timeit

def _randstr(n):
    ls = []
    for i in range(n):
        ls.append(random.choice(string.lowercase))
    return ''.join(ls)

def _sortstr(n):
    return ''.join(sorted(_randstr(n)))

def badstr(nish):
    res = ""
    for i in range(nish):
        res += _sortstr(i)
        if len(res) >= nish:
            break
    return res

def achampion(s):
    start = end = longest = 0
    best = ""
    for c1, c2 in izip_longest(s, s[1:]):
        end += 1
        if c2 and c1 <= c2:
            continue
        if (end-start) > longest:
            longest = end - start
            best = s[start:end]
        start = end
    return best

def bjorn(s):
    cur_start = 0
    cur_stop = 1
    long_start = cur_start
    long_end = cur_stop

    for ch in s[1:]:      
        if ch < s[cur_stop-1]:
            if (long_end-long_start) < (cur_stop-cur_start):
                long_start = cur_start
                long_end = cur_stop
            cur_start = cur_stop
        cur_stop += 1

    if (long_end-long_start) < (cur_stop-cur_start):
        return s[cur_start:cur_stop]
    return s[long_start:long_end]


def or1426(s):
    longest = [s[0]]
    current = [s[0]]
    for char in s[1:]:
        if char >= current[-1]: # current[-1] == current[len(current)-1]
            current.append(char)
        else:            
            current=[char]
        if len(longest) < len(current):
            longest = current
    return ''.join(longest)

if __name__ == "__main__":
    print 'achampion:', round(min(timeit.Timer(
        "achampion(rstr)",
        setup="gc.enable();from __main__ import achampion, badstr; rstr=badstr(30000)"
    ).repeat(15, 50)), 3)

    print 'bjorn:', round(min(timeit.Timer(
        "bjorn(rstr)",
        setup="gc.enable();from __main__ import bjorn, badstr; rstr=badstr(30000)"
    ).repeat(15, 50)), 3)

    print 'or1426:', round(min(timeit.Timer(
        "or1426(rstr)",
        setup="gc.enable();from __main__ import or1426, badstr; rstr=badstr(30000)"
    ).repeat(15, 50)), 3)

输出：

achampion: 0.274
bjorn: 0.253
or1426: 0.486

将数据更改为随机数据：

achampion: 0.350
bjorn: 0.337
or1426: 0.565

并排序：

achampion: 0.262
bjorn: 0.245
or1426: 0.503

“不，不，它还没死，它正在休息”