[leetcode] - 최대 하위 순서 와 (leetcode 53)
정수 배열 nums 를 지정 하고 최대 와 연속 하위 배열 (하위 배열 은 최소 하나의 요 소 를 포함 합 니 다) 을 찾 아 최대 와 합 을 되 돌려 줍 니 다.
출력: 6
해석: 연속 서브 배열 [4, - 1, 2, 1] 의 것 과 최대, 6.
분 치 법
원 배열 을 좌우 두 부분 으로 나 누고 요소 수 는 n / 2 이 며 가장 큰 하위 배열 의 아래 를 i 로 표시 하고 j 는 i 와 j 의 상황 을 세 가지 로 나 누 었 다.
상기 세 가지 상황 에 따라 분 치 전략 을 구축 하고 왼쪽 부분의 최대 서브 배열, 오른쪽 부분의 최대 서브 배열 과 mid 를 뛰 어 넘 는 최대 서브 배열 을 비교 한 다음 에 상기 세 개의 최대 서브 배열 을 비교 하여 최대 치 를 취한 다. 즉, 주어진 배열 의 최대 서브 배열 이다.
// mid
// i，j mid， mid， mid+1
FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
// mid
left-sum=MIN //
sum=0
max-left//
for i=mid to low
sum=A[i]+sum
if sum>left-sum
max-left=i
left-sum=sum
// mid
right-sum=MIN
sum=0
max-right
for j=mid+1 to high
sum=A[j]+sum
if sum>right-sum
max-right=j
right-sum=sum
return(max-left,max-right,left-sum+right-sum)
// A
FIND-MAXIMUM-SUBARRAY(A,low,high)
if low==high
return(low,high,A[low])// ，
else
mid=(low+high)/2
(left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid)
(right-low,right-high,right-sum)=FIND-MAXIMUM-SUBARRAY(A,mid+1,high)
(corss-low,cross-high,cross-sum)=FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
if left-sum>right-sum and left-sum>corss-sum
return (left-low,left-high,left-sum)
else if right-sum>left-sum and right-sum>corss-sum
return (right-low,right-high,right-sum)
else
return (cross-low,cross-high,cross-sum)#include
#include
#include
using namespace std;
typedef tuple resultType;
resultType FindMaxCrossSubarray
(int *A,int low,int mid,int high)
{
int left_max =mid;
long long leftMaxSum = LLONG_MIN;
long long sum=0;
for(int i = mid;i>=low;--i)
{
sum=sum+A[i];
if(sum>leftMaxSum)
{
left_max = i;
leftMaxSum = sum;
}
}
int right_max = mid+1;
long long rightMaxSum=LLONG_MIN;
sum = 0;
for(int j=mid+1;j<=high;++j)
{
sum=sum+A[j];
if(sum>rightMaxSum)
{
right_max = j;
rightMaxSum = sum;
}
}
return {left_max,right_max,leftMaxSum+rightMaxSum};
}
resultType FindMaxSubArray(int *A,int low,int high)
{
if(low == high)
{
return {low,high,A[low]};
}
else
{
int mid = (low+high)/2;
resultType leftResult = FindMaxSubArray(A,low,mid);
resultType rightResult = FindMaxSubArray(A,mid+1,high);
resultType crossResult = FindMaxCrossSubarray(A,low,mid,high);
if(get<2>(leftResult)>get<2>(rightResult)&&get<2>(leftResult)>get<2>(crossResult))
{
return leftResult;
}
else if(get<2>(rightResult)>get<2>(leftResult)&&get<2>(rightResult)>get<2>(crossResult))
{
return rightResult;
}
else
{
return crossResult;
}
}
}
int main()
{
int test[9]{-2,1,-3,4,-1,2,1,-5,4};
resultType result = FindMaxSubArray(test,0,sizeof(test)/sizeof(int)-1);
for(int i=get<0>(result);i<=get<1>(result);i++)
{
cout<(result);
system("pause");
return 0;
} FIND-MAX-SUBARRAY(A,low,high)
if low==high
return (A[low],A[low],A[low],A[low])// lsum，rsum，isum，msum
else
mid = (low+high)/2
(l_lsum,l_rsum,l_isum,l_msum)=FIND-MAX-SUBARRAY(A,low,mid)
(r_lsum,r_rsum,r_isum,r_msum)=FIND-MAX-SUBARRAY(A,mid+1,high)
lsum=l_lsum>(l_isum+r_lsum) ? l_lsum :l_isum+r_lsum
rsum=r_rsum>(r_isum+l_rsum) ? r_rsum:r_isum+l_rsum
isum=l_isum+r_isum
if l_msum>r_msum and l_msum>(l_rsum+r_lsum)
return (lsum,rsum,isum,l_msum)
if r_msum>l_msum and r_msum>(l_rsum+r_lsum)
return (lsum,rsum,isum,r_msum)
else
return (lsum,rsum,isum,l_rsum+r_lsum)#include
#include
using namespace std;
using resultType = tuple;
resultType FindMaxSubArray(int *A,int low,int high)
{
if(low==high)
{
return {A[low],A[low],A[low],A[low]};
}
else
{
int mid = (low+high)/2;
resultType lResult =FindMaxSubArray(A,low,mid);
resultType rResult =FindMaxSubArray(A,mid+1,high);
int l_lsum = get<0>(lResult),
l_rsum = get<1>(lResult),
l_isum = get<2>(lResult),
l_msum = get<3>(lResult);
int r_lsum = get<0>(rResult),
r_rsum = get<1>(rResult),
r_isum = get<2>(rResult),
r_msum = get<3>(rResult);
int lsum = l_lsum > (l_isum+r_lsum) ? l_lsum :l_isum+r_lsum;
int rsum = r_rsum > (r_isum+l_rsum) ? r_rsum:r_isum+l_rsum;
int isum = l_isum+r_isum;
if(l_msum>r_msum && l_msum>(l_rsum+r_lsum))
{
return {lsum,rsum,isum,l_msum};
}
else if(r_msum>l_msum && r_msum>(l_rsum+r_lsum))
{
return {lsum,rsum,isum,r_msum};
}
else
{
return {lsum,rsum,isum,l_rsum+r_lsum};
}
}
}
int GetMaxSubArrayValue(int *A,int low,int high)
{
resultType result = FindMaxSubArray(A,low,high);
return get<3>(result);
}
int main()
{
int test[9]{-2,1,-3,4,-1,2,1,-5,4};
int result = GetMaxSubArrayValue(test,0,sizeof(test)/sizeof(int)-1);
cout< FIND-MAX-SUBARRAY(A,low,high)
cursum=MIN//
curleft=0//
maxsum=MIN//
maxleft=0//
maxright=0//
for i=low to high
if cursum<0
cursum=A[i]
curleft=i
else
cursum=cursum+A[i]
if cursum>maxsum
maxsum=cursum
maxleft=curleft
maxright=i
return (maxsum,maxleft,maxright)#include
#include
#include
using namespace std;
using ResultType=tuple;
ResultType FindMaxSubArray(int *A,int low,int high)
{
long long cursum = LLONG_MIN;
int curleft = 0;
long long maxsum = LLONG_MIN;
int maxleft = 0;
int maxright = 0;
for(int n=low;n<=high;++n)
{
if(cursum<0)
{
cursum=A[n];
curleft=n;
}
else
{
cursum+=A[n];
}
if(cursum>maxsum)
{
maxsum = cursum;
maxleft = curleft;
maxright = n;
}
}
return {maxsum,maxleft,maxright};
}
int main()
{
int test[9]{-2,1,-3,4,-1,2,1,-5,4};
ResultType result = FindMaxSubArray(test,0,sizeof(test)/sizeof(int)-1);
for(int i=get<1>(result);i<=get<2>(result);i++)
{
cout<(result);
system("pause");
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
