LeetCode 978. 最長乱流サブ配列(C++、python)
2338 ワード
A
のサブ配列A[i], A[i+1], ..., A[j]
が以下の条件を満たす場合、乱流サブ配列と呼ぶ.i <= k < j
の場合、k
が奇数の場合、A[k] > A[k+1]
であり、k
が偶数の場合、A[k] < A[k+1]
である.i <= k < j
の場合、k
が偶数の場合、A[k] > A[k+1]
、k
が奇数の場合、A[k] < A[k+1]
.すなわち、比較シンボルがサブ配列内の各隣接要素ペア間で反転する場合、サブ配列は乱流サブ配列である.
A
の最大乱流サブ配列の長さを返します.例1:
:[9,4,2,10,7,8,8,1,9]
:5
:(A[1] > A[2] < A[3] > A[4] < A[5])
例2:
:[4,8,12,16]
:2
例3:
:[100]
:1
ヒント:
1 <= A.length <= 40000
0 <= A[i] <= 10^9
C++
class Solution {
public:
int maxTurbulenceSize(vector& A)
{
int n = A.size();
int res = 1;
int tmp = 1;
int flag;
for (int i = 1; i A[i - 1])
{
tmp++;
flag = 1;
}
else if (A[i] < A[i - 1])
{
tmp++;
flag = -1;
}
else
{
flag = 0;
}
res = max(tmp, res);
}
else
{
if (A[i] > A[i - 1])
{
if (-1 == flag)
{
tmp += 1;
res = max(tmp, res);
}
else
{
tmp = 2;
}
flag = 1;
}
else if (A[i] < A[i - 1])
{
if (1 == flag)
{
tmp += 1;
res = max(tmp, res);
}
else
{
tmp = 2;
}
flag = -1;
}
else
{
tmp = 1;
flag = 0;
}
}
}
return res;
}
};
python
class Solution:
def maxTurbulenceSize(self, A):
"""
:type A: List[int]
:rtype: int
"""
n=len(A)
res=1
tmp=1
flag=1
for i in range(1,n):
if 1==i:
if A[i]>A[i-1]:
tmp+=1
flag=1
elif A[i]A[i-1]:
if -1==flag:
tmp+=1
res=max(res,tmp)
else:
tmp=2
flag=1
elif A[i]