플러스 마이너스 합 최대
면접 대비시간 제한1초메모리 제한1024 MB
수열이 주어질 때, 각 항의 부호가 왼쪽 끝에서의 거리에 따라 정해지는 교대 합을 모든 부분 배열에 대해 최대화한다.
문제
길이 의 수열 에 대해 함수 은
로 정의된다.
을 만족하는 모든 정수 순서쌍 에 대하여 의 최댓값을 구하여라.
입력
첫째 줄에 이 주어진다.
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
출력
첫째 줄에 의 최댓값을 출력한다.
시간 제한1초메모리 제한1024 MB
수열이 주어질 때, 각 항의 부호가 왼쪽 끝에서의 거리에 따라 정해지는 교대 합을 모든 부분 배열에 대해 최대화한다.
길이 N의 수열 A에 대해 함수 f(l,r)은
f(l,r)=∑_i=lr(−1),i−lA_i
로 정의된다.
(1≤l≤r≤N)을 만족하는 모든 정수 순서쌍 (l,r)에 대하여 f(l,r)의 최댓값을 구하여라.
첫째 줄에 N이 주어진다. (1≤N≤200,000)
둘째 줄에 N개의 정수 A_1,A_2,…,A_N이 공백으로 구분되어 주어진다. (−109≤A_i≤109)
첫째 줄에 f(l,r)의 최댓값을 출력한다.
예제 1
5 -1 2 -4 -2 3
6