议事大厅-【赛码网】..

def solution(A):
    if len(A) == 0: return [-1,-1]
    res = []
    p,q,r = 0,0,0
    while(p<len(A)-1 and r<len(A)-1 and q<len(A)-1):
        q += 1
        if A[p] < A[q]:
            tmp1 = p
            while A[p] < A[q]:
                q += 1
                p += 1
                if q > len(A)-1:
                    break
           
            p = tmp1
           
            r = q
            q -= 1
            tmp2 = q
            if r > len(A)-1:
                break
            
            while (A[q] > A[r]):
                r += 1
                q += 1
                if r > len(A)-1:
                    break
            r -= 1
            q = tmp2
            res.append([p,q,r])
            p,q = r,r
        else:
            p = q
    if len(res) == 0: return [-1,-1]
    res1 = []
    for i in range(len(res)):
        res1.append([i,res[i][2]-res[i][0]])
    res2 = res1[0]
    
    for key,value in res1:
        if value > res2[1]:
            res2[0] = key
            
    return res[res2[0]][0],res[res2[0]][2]
    

n = raw_input()
A = raw_input()
n = int(n)
A = A.split(' ')
A = [int(i) for i in A]
res = solution(A)
print res[0],res[1]

我想拿个offer啊

我觉得超时吧

2017-03-30 21:18

acmcoderilIBYr6d

我是找断点做的。你可以试试看

2017-03-30 21:24

coder_KMPX6KBV

哪有那么麻烦，其实这道题在输入数组的头插入一个略大于头的数，在尾插入一个略大于尾的数，剩下的就是完完全全的贪心了，只要找到最低点就记录下标，最后再遍历一遍就可以了。（你可以考虑一下，这种做法不论如何找到的都是最低点，算两个最低点之间的长度，用前项减去后项就可以了。）

我的C++代码如下：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> A(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    A[0] = A[1] + 1;
    A[n + 1] = A[n] + 1;

    vector<int> down;
    for (int i = 1; i <= n; i++) {
        if (A[i] < A[i - 1] && A[i] < A[i + 1]) {
            down.push_back(i - 1);
        }
    }
    
    int minp = 0, maxp = 0;
    int maxlen = 0;

    for (int i = 0; i < down.size() - 1; i++) {
        int len = down[i + 1] - down[i];
        if (maxlen < len) {
            maxlen = len;
            minp = down[i];
            maxp = down[i + 1];
        }
    }

    if (maxlen < 2) {
        minp = maxp = -1;
    }
    cout << minp << " " << maxp << endl;

    return 0;
}

仅供参考，反正我还是想了一会儿才出此下策！！！

2017-03-30 21:34

小网

我感觉可以枚举中间那种转折点，往前走多少，往后走多少，这个简单dp就可以然后搞出最优答案

2017-03-30 21:39