알고스팟 maxsum 문제 파이썬으로 풀기

문제

문제는 주어진 정수 배열에서 가장 큰 부분합을 구하는 것이다.

 

문제를 처음 봤을 땐 0보다 작은 수의 위치를 구해 양수 및 0이 있는 배열만을 뽑아 그 중 최대치를 구하면 될 거 같다는 생각이 들었다.

그런데 예를 들어 -1 99 -1 99 이런식으로 배열이 주어졌을 때 최대의 부분합은 99 -1 99를 더한 197이다. 하지만 내가 생각한 것으로 구하면 99가 최대라고 계산하게 된다.

이렇게 음수를 포함하는 것도 가장 큰 부분합을 구하는데 영향을 줄 수 있어서 고민하다가 

출처: https://devmoons.tistory.com/entry/%EC%B5%9C%EB%8C%80-%EC%97%B0%EC%86%8D-%EB%B6%80%EB%B6%84%ED%95%A9-%EC%B0%BE%EA%B8%B0

이 글을 보고 이대로 코드를 짜보기로 했다.

내가 짠 코드

출력도 잘 이루어진다.

제출해보니

시간이 엄청 걸리긴 했지만 정답이 떳다.

 

느낀점:

1. 양수만 합하는 변수와 다 합하는 변수를 같이 이용해 거기서 최댓값을 구한 것처럼 문제를 구할 때 하나만을 구하지 않고 여러개를 구해 거기서 답을 도출하는 방법을 구하는 것을 다른 문제를 풀때도 생각해 보는것이 도움이 될 거 같다.

2. 다른 문제를 풀때보다 시간이 엄청 걸렸는데 (파이썬이 느린 언어이긴 해도 다른 문제를 풀 때 내 풀이는 수행시간이 세자리가 나온다... 네자리수는 이번이 처음) 이걸 좀 더 줄이는 알고리즘을 생각해 봐야겠다.