동적 계획 방법 최대 서브 연속 배열 곱 하기

배열 이 a [] 라 고 가정 하고 동 귀 를 직접 이용 하여 해 를 구한다. 음수 가 존재 할 수 있 는 상황 을 고려 하여 우 리 는 Max 로 a 로 끝 나 는 최대 연속 서브 문자열 의 곱 하기 값 을 표시 하고 Min 으로 a 로 끝 나 는 최소 서브 문자열 의 곱 하기 값 을 표시 한다. 그러면 상태 전이 방정식 은 Max = max {a, Max [i - 1] * a, Mini - 1] * a} 이다.Min=min{a, Max[i-1]*a, Min[i-1]*a}; 초기 상 태 는 Max [1] = Min [1] = a [1] 입 니 다.코드 는 간단 합 니 다:

double func(double *a,const int n)  
{  
    double *maxA = new double[n];  
    double *minA = new double[n];  
    maxA[0] = minA[0] =a[0];  
    double value = maxA[0];  
    for(int i = 1 ; i < n ; ++i)  
    {  
        maxA[i] = max(max(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);  
        minA[i] = min(min(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);  
        value=max(value,maxA[i]);  
    }  
    return value;  
}  

그 밖 에 이 문 제 는 또 다른 변종 형식 도 있다. 즉, 길이 가 N 인 정수 배열 을 정 하고 곱셈 만 허용 하 며 나눗셈 으로 임 의 (N - 1) 개수 의 조합 에서 곱 하기 가 가장 큰 그룹 을 계산 하고 알고리즘 의 시간 복잡 도 를 쓸 수 없다.실현 방법 은 바로 공간 이 시간 을 바 꾸 고 세 개의 데이터 p [], s [], t [] 를 정의 하 는 것 이다. 그 중에서 s [i] 에 배열 전 i 개 요소 의 곱 을 저장 하고 t [i] 에 저 장 된 N - i 개 요소 의 곱 을 정의 하면 p [i] = s [i - 1] * t [i + 1] 을 얻 을 수 있다.