동적 계획 – 최대 하위 섹션 및
1969 단어 동적 기획최대 하위 세그먼트 및
#include <stdio.h>
int MaxSum(int n, int *a, int *besti, int *bestj)
{
int sum = 0, i,j,k, thissum;
for(i = 0; i < n; i++)
{
for(j=0; j < n; j++)
{
thissum = 0;
for(k = i; k <= j; k++) thissum += a[k];
if(thissum > sum)
{
sum = thissum;
*besti = i;
*bestj = j;
}
}
}
return sum;
}
int MaxSum_2(int n, int *a, int *besti, int *bestj)
{
int sum = 0, i, j, thissum;
for(i = 0; i < n; i++)
{
thissum = 0;
for(j = i; j < n; j++)
{
thissum += a[j];
if(thissum > sum)
{
sum = thissum;
*besti = i;
*bestj = j;
}
}
}
return sum;
}
int MaxSubSum(int *a, int left, int right)
{
int sum = 0, center, leftSum, rightSum;
int i, lefs = 0, s1 = 0, rights = 0, s2 = 0;
if(left==right) sum=a[left] >0?a[left]:0;
else{
center = (left+right)/2;
leftSum = MaxSubSum(a, left, center);
rightSum = MaxSubSum(a, center+1, right);
for(i = center; i>=left; i--)
{
lefs += a[i];
if(lefs>s1) s1 = lefs;
}
for(i = center+1; i<=right; i++)
{
rights += a[i];
if(rights > s2) s2 = rights;
}
sum = s1+s2;
if(sum < leftSum) sum = leftSum;
if(sum < rightSum) sum = rightSum;
}
return sum;
}
int MaxSum_3(int n,int *a)
{
return MaxSubSum(a,0, n-1);
}
int MaxSum_4(int n, int *a)
{
int sum = 0, b = 0 ,i;
for(i = 0; i < n; i++)
{
if(b > 0) b+=a[i];
else b = a[i];
if(b > sum) sum = b;
}
return sum;
}
int main()
{
int a[]={-2,11,-4,13,-5,-2};
int left, right, sum;
//sum = MaxSum(6, a, &left, &right);printf("MaxSum = %d, left = %d, right = %d
",sum,left, right);
//sum = MaxSum_2(6, a, &left, &right);printf("MaxSum = %d, left = %d, right = %d
",sum,left, right);
//sum = MaxSum_3(6,a);printf("MaxSum = %d
",sum);
sum = MaxSum_4(6,a);printf("MaxSum = %d
",sum);
system("pause");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.