극성 뒤집기
골드 V의견: 0
길이 \(n\) 인 수열 \(a_1, a_2, \dots, a_n\) 이 있다. 각 원소는 \(0\) 이 아닌 정수이며 음수일 수도 있다. 다음 연산을 최대 \(n\) 번 수행할 수 있다(한 번도 하지 않아도 된다).
- 현재 \(a_i > 0\) 인 인덱스 \(i\) (\(1 \le i \le n\)) 를 하나 고른다.
- 그 후 모든 \(j\) (\(1 \le j \le i\)) 에 대해 \(a_j := -a_j\) 로 바꾼다. 즉, 앞에서부터 \(i\) 개의 부호를 한꺼번에 뒤집는다.
연산을 적절히 수행하여, 마지막에 수열의 모든 원소의 합이 최대가 되도록 하고 싶다. 얻을 수 있는 합의 최댓값을 구하여라.
\(2 \le n \le 2 \cdot 10^5\)
\(-10^9 \le a_i \le 10^9\), \(a_i \ne 0\)
첫째 줄에 수열의 길이 \(n\) 이 주어진다.
둘째 줄에 \(n\) 개의 정수 \(a_1, a_2, \dots, a_n\) 이 공백으로 구분되어 주어진다.
연산을 마친 뒤 얻을 수 있는 원소들의 합의 최댓값을 한 줄에 출력한다.
4
3 -4 -2 5
4
\(i=1\) 을 골라 \([-3,-4,-2,5]\), 다시 \(i=4\) 를 골라 \([3,4,2,-5]\) 로 만들면 합은 \(3+4+2-5 = 4\) 이고 이것이 최댓값이다.
3
4 5 6
15
모든 원소가 이미 양수이므로 연산을 하지 않는 것이 최선이다. 합은 \(4+5+6 = 15\).
2
-2 -3
-5
양수인 원소가 없어 어떤 연산도 할 수 없다. 합은 그대로 \(-2 + (-3) = -5\) 이다.
riseoj 작성
출처 Original
평가 및 의견
극성 뒤집기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
극성 뒤집기