부분배열 고르기 2
시간 제한2초메모리 제한128 MB
부분 배열의 합과 최소값의 곱을 최대화하는 구간을 찾아 그 값과 시작, 끝 위치를 출력하는 문제입니다.
문제
길이가 N(1 <= N <= 100,000)인 1차원 배열 A[1], ..., A[N]이 있다.
1 <= i <= j <= N인 두 정수 i, j를 골라 부분배열 A[i], ..., A[j]를 만들 때, 이 부분배열의 점수는 다음과 같다.
(A[i] + ... + A[j]) * min{A[i], ..., A[j]}
즉, 부분배열의 원소 합에 그 부분배열의 최솟값을 곱한 값이 점수이다.
배열 A가 주어질 때, 가능한 부분배열 중 최대 점수를 구하고 그 점수를 만드는 구간을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N이 주어진다.
둘째 줄에는 A[1], ..., A[N]을 나타내는 정수 N개가 주어진다. 각 정수는 0 이상 1,000,000 이하이다.
출력
첫째 줄에 가능한 최대 점수를 출력한다.
둘째 줄에 그 점수를 만드는 구간의 시작 위치 i와 끝 위치 j를 출력한다.