백준)15673 헤븐스 키친 2

https://www.acmicpc.net/problem/15673

수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.

연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.

dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,

dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.

또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,

이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,

lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.

즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.

이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.

그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int n;
ll arr[100001];
 
ll dmin[100001], dmax[100001];
ll lmin[100001], lmax[100001];
ll rmin[100001], rmax[100001];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
 
    lmin[1] = lmax[1] = dmin[1] = dmax[1] = arr[1];
 
    for (int i = 2; i <= n; ++i) {
        if (dmax[i - 1] < 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i - 1] + arr[i];
 
        if (dmin[i - 1] > 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i - 1] + arr[i];
 
        lmin[i] = min(lmin[i - 1], dmin[i]);
        lmax[i] = max(lmax[i - 1], dmax[i]);
    }
 
    memset(dmin, 0, sizeof(dmin));
    memset(dmax, 0, sizeof(dmax));
 
    rmin[n] = rmax[n] = dmin[n] = dmax[n] = arr[n];
 
    for (int i = n - 1; i >= 1; --i) {
        if (dmax[i + 1] < 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i + 1] + arr[i];
 
        if (dmin[i + 1] > 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i + 1] + arr[i];
 
        rmin[i] = min(rmin[i + 1], dmin[i]);
        rmax[i] = max(rmax[i + 1], dmax[i]);
    }
 
    ll ans = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        ans = max(ans, lmin[i] * rmin[i + 1]);
        ans = max(ans, lmin[i] * rmax[i + 1]);
        ans = max(ans, lmax[i] * rmin[i + 1]);
        ans = max(ans, lmax[i] * rmax[i + 1]);
    }
 
    cout << ans;
}