LeetCode/Java/978.java at master · strengthen/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
__________________________________________________________________________________________________
sample 3 ms submission
class Solution {
    public int maxTurbulenceSize(int[] A) {
        return helper(A,0);
    }
    private int helper(int [] A,int index){
        if(index >= A.length - 1){
            return A.length - index;
        }
        int len =2;
        index+=2;
        int prev = A[index-1]  - A[index-2];
        if(prev == 0){
            int next = helper(A,index-1);
            return 1>next?1:next;
        }
        while(index<A.length){
            int d =A[index] - A[index-1];
            if(d == 0){
                break;
            }
            if((prev^d)<0){
                len++;
                index++;
                prev =d;
            }
            else{
                break;
            }
        }

        int next = helper(A,index-1);
        return next> len?next:len;
    }
}
__________________________________________________________________________________________________
sample 42196 kb submission
class Solution {
    public int maxTurbulenceSize(int[] A) {
        if(A.length == 1)
            return 1;
        int N = A.length;
        int res = 1,tmp = 1;
        int[] dp = new int[N];
        for(int i =0; i<N-1; i++){
            if(A[i] > A[i+1])
                dp[i] = 1;
            else if(A[i] < A[i+1])
                dp[i] = 0;
            else
                dp[i] = 2;
        }
        for(int i=0; i<N-1; i++){
            if(dp[i] == 2){
                res=Math.max(res, tmp);
                tmp=1;
            }else if(dp[i] == dp[i+1]){
                res=Math.max(res, tmp+1);
                tmp=1;
            }else{
                tmp++;
            }
        }
        return res;
    }
}
__________________________________________________________________________________________________