최대 연속 하위 시퀀스(HDU1223)(동적 계획)

1664 단어
Problem Description은 K의 정수를 나타내는 시퀀스 {N1, N2,..., NK}를 지정합니다. 임의의 연속 서브시퀀스는 {Ni, Ni+1,..., Nj}이고 여기서 1<=i <=j<=K입니다.최대 연속 서열은 모든 연속 서열 중 요소와 가장 큰 것이다. 예를 들어 주어진 서열 {-2,11,-4,13,-5,-2}이고 최대 연속 서열은 {11,-4,13}이며 최대 및 20이다.올해 데이터 구조 시험지에서 컴파일러가 가장 크고, 이 서열의 첫 번째 요소와 마지막 요소를 출력해야 한다는 요구가 추가되었다.
Input 테스트 입력에는 테스트 용례가 몇 개 포함되어 있으며, 각 테스트 용례는 두 줄을 차지하고, 첫 번째 줄은 정수 K (< 10000) 를 주고, 두 번째 줄은 K 개의 정수를 주며, 중간은 빈칸으로 구분한다.K가 0일 때 입력이 끝났습니다. 이 용례는 처리되지 않습니다.
Output은 모든 테스트 용례에 대해 1줄에서 최대, 최대 연속 서열의 첫 번째 요소와 마지막 요소를 출력하고, 중간에 빈칸으로 구분합니다.최대 연속 서열이 유일하지 않으면, 번호 i와 j의 가장 작은 것을 출력합니다. (예를 들어 예시를 입력한 2, 3조)모든 K 요소가 음수이면 최대 및 0을 정의하여 전체 시퀀스의 첫 번째 끝 요소를 출력합니다.
Sample Input6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20
Sample Output20 11 1310 1 410 3 510 10 100 -1 -20 0 0 
#include 
#include 
using namespace std;
const int N= 10000;
int a[N], dp[N], maxsum, maxstart, maxend;
 
void serach(int n)
{
    int sum, sumstart;
    
    maxsum = maxstart = maxend = a[0];
    sum = 0;
    for(int i = 0; i maxsum) 
        {
            maxsum = sum;
            maxstart = sumstart;
            maxend = a[i];
        }
    }
}
 
int main()
{
    int n;
    while(cin>>n&& n) 
    {
        for(int i=0; i>a[i];
 
        serach(n);
 
        if(maxsum < 0)
            cout<

Hue의 Remote API로 조명을 제어했어요.
대수 구조

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage