부분합을 이용하여 풀었습니다. 

sum[i] 에는 0부터 i번째 까지의 부분합을 담았고 

submin[i] 에는 sum 배열의 i 이하 원소중 최소값을 담아서 

최종적으로 모든 i에 대해 sum[i] - submin[i - 1] 의 최대값을 출력하도록 했습니다.

 여러가지 케이스를 테스트 해봤는데 다 정상적으로 나와서, 어떤 케이스가 틀린 것인지 궁금합니다.

indioindio   9달 전

정수범위의 최소값은 -INT_MAX가 아니라 -INT_MAX -1 인데 입력으로

1

-2147483648

같은게 들어오는지는 잘 모르겠네요.

res를 어떤 경계값으로 잡기보다는 첫번째 원소같은 걸로 해두고 푸는 것을 추천드립니다.

indioindio   9달 전

위에 든 예시는 틀리도록 제출해봤더니 틀리네요(ㅠㅠ)

저런 입력이 존재하는 것 같습니다.

답변 감사합니다.


말씀대로 고쳐봤는데.. 혹시 몰라서 자료형도 long long으로 했는데,

그래도 오답이 나네요.

혹시나해서 알고리즘이 틀려서 오답이 있는가 싶어서, 정답 코드와 제 코드를 가지고 랜덤 데이터를 무작위로 돌려봤는데, 모두 일치하더라구요..

ㅠㅠ 뭐가 문제인걸까요

indioindio   9달 전

음 여전히 자료범위에 관련된 문제인 것 같습니다.

100
-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648

더하다가 자료형의 문제로 합의 값이 양수가 되어버려서 양의 값을 출력하는 것 같네요.

indioindio   9달 전

위의 저런 입력이 들어 지는 모르겠지만 합의 값이 음수라면 더 이상 고려하지 않거나 하는 (음수까지의 합 다음에 어떤 양수가 나온다면 그 수 하나만 취하는 게 이득이겠죠) 등의 방법을 추가하셔야 할 것 같습니다.

답변 감사합니다. 많은 도움이 되었습니다


결국 다른 방법으로 풀 수 밖에 없나보네요..

indioindio   9달 전

네 조금 아쉽네요 정수자료형의 크기에 제한이 없는 언어라면 맞추셨을텐데요.


indioindio   9달 전

음 그리고 보니깐 알고리즘 자체에도 약간 문제가 있는 것 같습니다.

4000개의 양수로만 이루어진 랜덤입력에 대해서 오답을 출력하네요.

indioindio   9달 전

오... 잠시만요...

indioindio   9달 전

http://www.cplusplus.com/reference/ios/ios_base/sy...

에 의하면

With stdio synchronization turned off, iostream standard stream objects may operate independently of the standard C streams (although they are not required to), and mixing operations may result in unexpectedly interleaved characters.

라고 되어있네요. cout.sync_with_stdio(false); 를 켜고 cin, cout만 사용하거나 저 부분 없이 scan/ printf만 사용하셔야 할 것 같습니다.

랜덤생성으로는 입력부분을 거치지 않아서 발견할수가 없었던 모양입니다...ㅠ

indioindio   9달 전

확인 차 제출 해봤는데 양해 부탁드립니다.

와 대박.....

진짜 감사드립니다!!!

너무 열심히 도와주셔서 ㅜㅜ 덕분에 정답이라는 문구를 볼 수 있었습니다

감사합니다!!

indioindio   9달 전

별 말씀을요 저도 덕분에 하나 배워가네요 :)

댓글을 작성하려면 로그인해야 합니다.