C 언어 를 이용 하여 최대 연속 서브 시퀀스 곱 하기 방법 을 구하 다

제목 설명:부동 소수점 서열 을 주 고 최대 곱 하기 연속 하위 문자열 의 값 을 가 져 옵 니 다.예 를 들 어-2.5,4,0,3,0.5,8,-1 은 추출 한 최대 곱 하기 연속 하위 문자열 은 3,0.5,8 입 니 다.즉,상기 배열 중 3 0.58 이라는 3 개 수의 곱 하기 3*0.5*8=12 가 가장 크 고 연속 적 인 것 이다.
알림:이 최대 곱 하기 연속 하위 문자열 은 최대 곱 하기 하위 서열 과 다 르 므 로 헷 갈 리 지 마 십시오.전자 하위 문자열 은 연속 을 요구 하고 후자 하위 서열 은 연속 을 요구 하지 않 습 니 다.즉,가장 긴 공공 하위 문자열(Longest CommonSubstring)과 가장 긴 공공 하위 서열(Longest Common Subsequence,LCS)의 차이 점:
    하위 문자열(Substring)은 문자열 의 연속 적 인 부분 이 고,하위 시퀀스(Subsequence)는 시퀀스 의 순 서 를 바 꾸 지 않 으 며,시퀀스 에서 임의의 요 소 를 제거 하여 얻 은 새로운 시퀀스 입 니 다.
    더 간략하게 말하자면 전자(하위 문자열)의 문자 위 치 는 연속 되 어야 하고 후자(하위 서열 LCS)는 필요 하지 않다.예 를 들 어 문자열'acdfg'과'akdfc'의 가장 긴 공공 하위 문자열 은'df'이 고 그들의 가장 긴 공공 하위 서열 인 LCS 는'adf'이 며 LCS 는 동적 계획 법 으로 해결 할 수 있다.
해답:
    해법 1.궁 거,모든 계산 조합:
    아마도 독자 들 이 이 문 제 를 처음 보면 가장 큰 곱셈 서브 서열 문제 가 가장 큰 서브 배열 과 문제 와 유사 하 다 는 것 을 생각 하 게 될 것 이다.http://blog.csdn.net/v_JULY_v/article/details/6444021,아마도 즉시 가장 간단 하고 거 친 방식 으로:두 개의 for 순환 직접 폴 링 을 생각 할 것 이다.
    해법 2.최대 자 배열 과 문제 와 유사 하지만 실제 적 으로 구체 적 으로 처리 하면 많이 다르다.왜 냐 면 곱 하기 서브 시퀀스 에는 플러스 와 마이너스 가 있 고 0 이 있 을 수 있 기 때문이다.우 리 는 문 제 를 이렇게 간소화 할 수 있다.배열 에서 하위 서열 을 찾 아 곱 하기 가 가장 크다.동시에 하위 서열 을 찾 아 곱 하기 최소(음수 의 경우)를 합 니 다.비록 우 리 는 하나의 최대 적 만 있 으 면 되 지만 음수 의 존재 로 인해 우 리 는 이 두 개의 곱 하기 를 동시에 찾 아 하 는 것 이 오히려 편리 하기 때문이다.최대 곱 하기 뿐 아니 라 최소 곱 하기 도 기록 해 야 한 다 는 것 이다.So,우 리 는 max Current 에 현재 최대 곱 하기 candidate 를 표시 하고,minCurrent 는 반대로 현재 최소 곱 하기 candidate 를 표시 하 며,max Product 은 지금까지 의 모든 최대 곱 하기 candidates 의 최대 치 를 기록 합 니 다.(위 에서 candidate 라 는 단 어 를 사용 한 것 은 새로운 라운드 의 최대/최소 곱 하기 가 될 수 있 기 때 문 입 니 다.빈 집합 의 곱 하기 가 1 로 정의 되 기 때문에 배열 을 검색 하기 전에 max Current,minCurrent,max Product 는 모두 1 로 부 여 됩 니 다.
만약 에 언제든지 max Current 와 minCurrent 라 는 두 개의 최대/최소 곱 하기 candidates 가 있다 고 가정 하면 배열 의 요소 x(i)를 새로 읽 은 후에 새로운 최대 곱 하기 candidate 는 max Current 또는 minCurrent 와 x(i)의 곱 하기 중 큰 것 일 수 있 습 니 다.만약 에 x(i)<0 이 max Current    해법 3.본 문 제 는 상기 와 유사 한 최대 서브 배열 과 해법 을 제외 하고 동태 계획 으로 도 직접 해결 할 수 있다.(사실은 상기 해법 은 본질 적 으로 동태 계획 이기 도 하고 문제 풀이 에 나타 난 구체 적 인 형식 은 다음 의 해법 과 다 를 뿐이다.이 차이 점 은 바로 아래 의 해법 2 회 에서 동태 계획 문제 에서 흔히 볼 수 있 는 DP 방정식 을 쓰 고 해법 1 은 직접 구 해 하 는 것 이다.구체 적 인 해법 은 다음 과 같다.
    만약 에 배열 이 a[]라 고 가정 하고 동 귀 를 직접 이용 하여 해 를 구한다.음수 가 존재 할 수 있 는 상황 을 고려 하여 우 리 는 Max 로 a 로 끝 나 는 최대 연속 서브 꼬치 의 곱 수 치 를 나타 내 고 Min 으로 a 로 끝 나 는 최소 서브 꼬치 의 곱 수 치 를 나타 내 면 상태 전이 방정식 은 다음 과 같다.
       Max=max{a, Max[i-1]*a, Min[i-1]*a};
       Min=min{a, Max[i-1]*a, Min[i-1]*a};
 초기 상 태 는 Max[1]=Min[1]=a[1]입 니 다.
다음은 구체 적 인 ACM 문 제 를 살 펴 보 겠 습 니 다.
 제목.
    제목 설명: 
    부동 소수점 시퀀스(양수,0,음수 가 있 을 수 있 음)를 지정 하여 가장 큰 연속 서브 시퀀스 곱 하기 를 구하 십시오. 
    입력: 
    입력 은 여러 개의 테스트 샘플 을 포함 할 수 있 습 니 다. 
    각 테스트 샘플 의 첫 줄 은 정수 n(n<=100000)만 포함 하고 부동 소수점 서열 의 개 수 를 표시 합 니 다. 
    두 번 째 줄 은 n 개의 부동 소수점 을 입력 하여 빈 칸 으로 구분 합 니 다. 
    데 이 터 를 입력 하면 모든 숫자 곱 하기 가 쌍 정밀도 부동 소수점 이 표시 하 는 범위 내 에 있 음 을 보증 합 니 다. 
    출력: 
    모든 테스트 사례 에 대응 하여 출력 시퀀스 에서 가장 큰 연속 서브 시퀀스 곱 하기,곱 하기 가 부동 소수점 이면 2 비트 소 수 를 유지 하고,최대 곱 하기 가 마이너스 라면 출력-1. 
    샘플 입력:  

  7 
  -2.5 4 0 3 0.5 8 -1 
  5 
  -3.2 5 -1.6 1 2.5 
  5 
  -1.1 2.2 -1.1 3.3 -1.1 

    샘플 출력:  

  12 
  64 
  8.78 

사고의 방향
최대 연속 서브 시퀀스 곱 하기 와 최대 연속 서브 시퀀스 가 다 릅 니 다.여기 서 최대 연속 서브 시퀀스 와 최 적 화 된 구 조 를 기억 해 보 세 요.
최대 연속 서브 시퀀스 와
우 리 는 sum[i]로 arr[i]로 끝 나 는 최대 연속 서브 시퀀스 와 상태 전이 방정식 을 표시 합 니 다.

최대 연속 서브 시퀀스 곱 하기
마이너스 가 존재 하 는 상황(ps:마이너스 가 플러스 를 얻 을 수 있 음)을 고려 하여 우 리 는 두 개의 보조 배열,max[i]와 min[i],max[i]로 arr[i]로 끝 나 는 최대 연속 서브 시퀀스 곱 을 표시 하고 min[i]로 끝 나 는 최소 연속 서브 시퀀스 곱 을 표시 하기 때문에 상태 전이 방정식 은 다음 과 같다.

and

상태 전이 방정식 이 있 으 면 dp 코드 는 쉽게 실 현 됩 니 다.여기 서 이해 하지 못 하 는 학생 을 보면 알고리즘 학습 에 시간 을 많이 쓰 는 것 을 권장 합 니 다!
AC 코드
  

 #include <stdio.h> 
  #include <stdlib.h> 
    
  double maxNumInThree(double a, double b, double c) 
  { 
    double max; 
    max = (a > b) ? a : b; 
    max = (max > c) ? max : c; 
    
    return max; 
  } 
    
  double minNumInThree(double a, double b, double c) 
  { 
    double min; 
    min = (a < b) ? a : b; 
    min = (min < c) ? min : c; 
    
    return min; 
  } 
    
    
  int main(void) 
  { 
    int i, n; 
    double *arr, *max, *min, res; 
    
    while (scanf("%d", &n) != EOF) { 
      arr = (double *)malloc(sizeof(double) * n); 
      max = (double *)malloc(sizeof(double) * n); 
      min = (double *)malloc(sizeof(double) * n); 
      for (i = 0; i < n; i ++) 
        scanf("%lf", arr + i); 
    
      //                
      max[0] = min[0] = res = arr[0]; 
      for (i = 1; i < n; i ++) { 
        max[i] = maxNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]); 
        min[i] = minNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]); 
        if (max[i] > res) 
          res = max[i]; 
      } 
    
      if (res >= 0) { 
        //          
        if ((res - (int)res) == 0) 
          printf("%d
", (int)res); 
        else 
          printf("%.2lf
", res); 
      } else { 
        printf("-1
"); 
      } 
    
      free(arr); 
    } 
    
    return 0; 
  } 

       
    /**************************************************************
        Problem: 1501
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:110 ms
        Memory:4964 kb
    ****************************************************************/