배열 연산 서브태스크 1초 256MB
문제
길이 N 짜리 정수 배열 A[1], A[2], ..., A[N] 이 있다.
경규는 이 배열에 있는 N 개의 정수들의 합이 최대가 되도록 하고 싶어한다.
정수 K 가 주어지고, 경규는 "최대 1번" 이 배열의 값을 바꾸는 연산을 할 수 있는데, 그 연산은 다음과 같다.
' 두 자연수 L ,R ( 1 ≤ L ≤ R ≤ N ) 을 정하고, A[L], A[L+1], ... , A[R] 까지 ( R - L + 1 ) 개의 정수에 K 를 곱한다. '
( L == R 이라면 A[L] 에만 K 를 곱함 )
이 연산을 최대 1번 했을 때, 배열의 수들의 합의 최댓값을 출력하자.
입력
첫 줄에 두 정수 N 과 K 가 입력된다. ( 1 ≤ N ≤ 30만, -100만 ≤ K ≤ 100만 )
두 번째 줄에 N 개의 정수 A[1], ..., A[N] 이 입력된다. ( 각각 -100만 이상 100만 이하 )
출력
첫 줄에 가능한 배열의 수의 최댓값을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | K = 1 |
| #2 | 10점 | 모든 1 ≤ i ≤ N 에 대해, A[i] ≥ 0 |
| #3 | 20점 | 1 ≤ N ≤ 100 |
| #4 | 60점 | 제약 조건 없음 |
예제 #1
5 -1
-3 1 -2 -6 4
14
L = 1, R = 4 로 잡으면 배열은 3, -1, 2, 6, 4 가 되어 합이 14 가 된다.
이것이 최댓값이다.
예제 #2
5 100
-1 -2 -5 -4 -3
-15
연산을 하지 않는 것이 최선이다.
따라서 답은 입력된 5개의 수의 합인 -15 이다.
로그인해야 코드를 작성할 수 있어요.