编写一段有效的程序，求已知串中最长空格序列的长度，要求尽量少检查串的字符。
提示：空格序列长度增大，程度将变得更快。

有点抽象

看看

有一种思路就是一下：
    比如说前面已经知道了最长为7个，如果后面的第13个不为空格，就可以直接跳到第14个判断了，因为8和12之间的都不需要判断。
    不知道对你有没有用。
新手上路。多指教。

好像有点问题可以这样直接判断第15个，如果第15个不是则可以跳到16个重新开始，因为是要最长的长度。如果15个也是的话就看中间的，然后看后一段直至都是空格，如果其中有个不是空格就可以跳了。

网上有人说折半进行查找空格的，不知道对不对？

用zyy_hz说的方法写了一个程序，不知道合不合要求

#include <stdio.h>
#include <string.h>

/***********************************

 * 参数len: 字符串长度
            防止指针在间跳后越界 

 **********************************/
int max_blankarr(char *str, int len);

int main()
{
    char test[] = "The following string has 20 blankspaces:                    ";
    
    printf("The max blank arry length is %d.\n", max_blankarr(test, strlen(test)));
    
    return 0;
}

int max_blankarr(char *str, int len)
{
    int maxlen, index, i;
    
    for(maxlen = 0, index = 0; index+maxlen < len; index++){
        if(str[index] == ' ')
            if(str[index+maxlen] == ' '){
                i = 1;
                while(++index < len && str[index] == ' ') ++i;
                (i > maxlen)? maxlen = i : maxlen;
            }
            else index += maxlen;
    }
    
    return maxlen;
}

上面的max_blankarr函数重新优化了一下，这样效率比刚才那个要高

int max_blankarr(char *str, int len)
{
    int maxlen, index, i;
    
    for(maxlen = 0, index = 0; index+maxlen < len; index++){
        if(str[index+maxlen] != ' ')
            index += maxlen;
        else
            if(str[index] == ' '){
                i = 1;
                while(++index < len && str[index] == ' ') ++i;
                (i > maxlen)? maxlen = i : maxlen;
            }
    }
    
    return maxlen;
}

我不信能有比O(n)更高效的算法。要求尽量少检查串的字符，但每个字符至少得检查一次吧。提示更是莫名其妙。

int blank_len(char *s)
{
    int max, c;
    for(max = c = 0; *s; s++)
        if(*s == ' ') c++;
        else
        {
            if(max < c) max = c;
            c = 0;
        }
    return max > c ? max : c;
}

[ 本帖最后由 beyondyf 于 2013-2-20 19:54 编辑 ]

楼上的回答欠考虑，关于这个问题每个字符都检查一遍是最低效的实现方法
其实存在许多不必要的比较可以优化掉的
当已经搜索到最长为n的连续空格时，继续搜索时如果当前位置后n+1处的字符不为空格，则这段字符至多为n个连续的空格
完全可以跳过不比较，当连续空格越长时这样的优势会更明显
举个例子来说：“a__b__f”,'_'表示空格
当我们检查到b的时候，就已经知道最大长度至少是2，那么接着只要直接看后面2+1处的字符，即f，不是空格，那么b后面到f这一段至多只有2个连续空格
就可以不用搜索，这里就有了优化的空间

收到的鲜花

• beyondyf 于 2013-02-20 20:52 送鲜花  50朵   附言：感谢指正，确实是我欠考虑了