하위 배열 의 최대 인 스 턴 스 코드 를 구하 십시오.

1009 단어 배열최대
제목:성형 배열 을 입력 하 십시오.배열 에는 양수 도 있 고 마이너스 도 있 습 니 다.배열 에서 연속 되 는 하나 또는 여러 개의 정수 가 하나의 키 배열 을 구성 하고 모든 하위 배열 은 하나의 합 이 있다.모든 하위 배열 의 합 의 최대 치 를 구하 십시오.시간 복잡 도 를 O(n)로 요구 합 니 다.
예 를 들 어 입력 한 배열 은 1,-2,3,10,-4,7,2,-5 이 고 가장 큰 하위 배열 은 3,10,-4,7,2 이기 때문에 이 하위 배열 의 것 과 18 로 출력 된다.
상태 이동 방정식 을 찾 았 습 니 다.dp[i]는 앞의 i 개 수 에서 i 를 포함 하 는 하위 배열 의 최대 합 을 표시 합 니 다.i 번 째 숫자 가 가장 크 거나 i-1 을 포함 하 는 하위 배열 의 최대 크기 와(즉 dp[i-1])를 결합 해 야 합 니 다.즉,dp[i]=max{arr[i],dp[i-1]+arr[i]};
코드 는 다음 과 같다.

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

int res(int* arr, int len){
    // :)
    int max = -(1<<31);
    int i;
    for(i=1;i<len;i++){
        arr[i] = max(arr[i],arr[i-1]+arr[i]);
        if(max < arr[i]) max = arr[i];
    }
    return max;
}

int main(){
    int arr[] = {1,-2,3,10,-4,7,2,-5};
    printf("%d
",res(arr,8));
    return 0;
}

좋은 웹페이지 즐겨찾기