[9 도] 제목 1376: 최근 제로 서열

제목 1376: 최근 제로 시퀀스
시간 제한: 1 초 메모리 제한: 32 조 특수 판정 문제: 제출 여부: 367 해결: 94
제목 설명:
정수 서열 을 정 하면 최대 문자열 과 합 을 구 할 수 있 습 니까?거의 모든 데이터 구조 와 알고리즘 은 최대 하위 문자열 과 알고리즘 을 설명 합 니 다.오늘 은 최근 0 자 꼬치 와 정수 서열 에서 0 에 가장 가 까 운 연속 자 꼬치 를 계산 해 보 자.예 를 들 어 정수 서열 6, - 4, 5, 6 에서 연속 서브 꼬치 (- 4, 5 곶 의 합 은 1 로 다른 어떤 연속 서브 꼬치 의 합 보다 0 에 가깝다.이 정수 서열 의 최근 0 자 꼬치 와 1 이다.
입력:
각 테스트 파일 은 여러 개의 테스트 사례 를 포함 하고 모든 테스트 사례 두 줄 을 포함한다. 첫 번 째 줄 은 하나의 정수 N 을 포함 하고 정수 서열 의 길 이 를 대표 하 며 두 번 째 줄 은 빈 칸 으로 구 분 된 N 개의 정수 로 이 정수 서열 을 대표 한다.그 중에서 우 리 는 1 < = N < = 105 를 보장 할 수 있 고 모든 정 수 는 － 230 보다 크 며 230 보다 작다.
출력:
모든 정수 시퀀스 에 대해 한 줄 을 출력 하고 하나의 정 수 를 포함 합 니 다. 즉, 최근 0 개의 문자열 과.만약 에 여러 개의 해 (예 를 들 어 - 1, 3, 1 에 - 1 과 1 두 개의 해 가 존재 한다) 가 동시에 존재 한다 면 가장 큰 하 나 를 출력 한다 (출력 1).
샘플 입력:
4
6 －4 5 6
2
－1 1
샘플 출력:
1
0
질의 응답:
문제 풀이 에 문제 가 생 겼 다 고요?문제 풀이 소감 공유?이 문 제 를 토론 하려 면 방문 하 십시오.http://t.jobdu.com/thread-8099-1-1.html
문제 풀이 방향:
폭력 검색, 모든 하위 문자열 의 합 을 구하 세 요.단일 요소 의 값 이 0 이면 0 을 직접 출력 하면 됩 니 다.
Java AC

import java.util.Scanner;
 
public class Main {
    /*
     * 1376
     */
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int array[] = new int[n];
            int result = -1;
            for (int i = 0; i < n; i++) {
                array[i] = scanner.nextInt();
                if (array[i] == 0) {
                    result = 0;
                }
            }
            if (result == 0) {
                System.out.println(result);
                continue;
            }
            result = array[0];
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = i; j < n; j++) {
                    sum += array[j];
                    int tempSum1 = Math.abs(sum);
                    int tempSum2 = Math.abs(result);
                    if (tempSum1 < tempSum2
                            || (tempSum1 == tempSum2 && sum > result)) {
                        result = sum;
                        if (result == 0) {
                            break;
                        }
                    }
                }
                if (result == 0) {
                    break;
                }
            }
            System.out.println(result);
        }
    }
}
 
/**************************************************************
    Problem: 1376
    User: wangzhenqing
    Language: Java
    Result: Accepted
    Time:1730 ms
    Memory:105284 kb
****************************************************************/

C++ AC

#include <stdio.h>
 
const int maxn = 100005;
int array[maxn];
 
int abs(int x){
    return x < 0 ? x * -1 : x;
}
int main(){
    int n,i,j;
    while(scanf("%d",&n) != EOF){
        int result = -1;
        for(i = 0; i < n; i++){
            scanf("%d",array+i);
            if(array[i] == 0){
                result = 0;
            }
        }
        if(result == 0){
            printf("%d
",result);
            continue;
        }
        result = array[0];
        for (i = 0; i < n; i++) {
            int sum = 0;
            for (j = i; j < n; j++) {
                sum += array[j];
                int tempSum1 = abs(sum);
                int tempSum2 = abs(result);
                if (tempSum1 < tempSum2
                        || (tempSum1 == tempSum2 && sum > result)) {
                    result = sum;
                    if (result == 0) {
                        break;
                    }
                }
            }
            if (result == 0) {
                break;
            }
        }
        printf("%d
",result);
    }
    return 0;
}
/**************************************************************
    Problem: 1376
    User: wangzhenqing
    Language: C++
    Result: Accepted
    Time:140 ms
    Memory:1412 kb
****************************************************************/