【单调栈/dp】Max answer

Describe

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer n(1≤n≤5*10^5)

Second line contains integers represent the array a(−10^5≤ai≤10^5)

Output

One line contains an integer represent the answer of the array.

样例输入

5

1 2 3 4 5

样例输出

36

题意
给你一个序列,对于每个连续子区间,有一个价值,等与这个区间和×区间最小值,
求所有子区间的最大价值是多少。

一开始是想的用DP做,结果超时600ms,,一直优化到最后也没过,原来是正解单调栈,自闭。。

超时DP代码:

#include<cstdio>
#include <algorithm>
using namespace std;
int arr[5 * (int)(10e5) + 10];
int dp[5 * (int)(10e5) + 10];
int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  dp[0] = arr[0];
  for (int i = 1; i < n; i++)//前i个数
  {
    int sum = arr[i];
    for (int j = 1; j <= i; j++)
    {
      sum += arr[i - j];
      dp[i] = max(dp[i],max(dp[i - 1], *min_element(arr + (i - j),arr+i+1)*sum));
    }
    dp[i] = max(dp[i], arr[i]);
  }
  printf("%d", dp[n - 1]);
}

 

单调栈代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000+10;
const LL inf = 1e17;

int n;
int i,j;
LL sum[maxn],stmx[maxn][23],stmn[maxn][23];
int a[maxn],l[maxn],r[maxn];

stack<int> sta;

LL askmx(int l,int r)
{
    int k=log2(r-l+1);
    return max(stmx[l][k],stmx[r-(1<<k)+1][k]);
}

LL askmn(int l,int r)
{
    int k=log2(r-l+1);
    return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}

int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++) sum[i]=sum[i-1]+(LL)a[i];
    for (i=0;i<=n;i++) stmx[i][0]=stmn[i][0]=sum[i];
    for (j=1;(1<<j)<=n+1;j++)
    {
        for (i=0;i+(1<<j)-1<=n;i++)
        {
            stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<(j-1))][j-1]);
            stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<(j-1))][j-1]);
        }
    }
    for (i=1;i<=n;i++)
    {
        while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
        if (sta.empty()) l[i]=1; else l[i]=sta.top()+1;
        sta.push(i);
    }
    while (!sta.empty()) sta.pop();
    for (i=n;i>=1;i--)
    {
        while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
        if (sta.empty()) r[i]=n; else r[i]=sta.top()-1;
        sta.push(i);
    }
    LL ans=-inf;
    for (i=1;i<=n;i++)
    {
        if (a[i]<0)
        {
            LL R=askmn(i,r[i]);
            LL L=askmx(l[i]-1,i-1);
            ans=max(ans,(R-L)*(LL)a[i]);
        } else
        if (a[i]>0)
        {
            LL R=askmx(i,r[i]);
            LL L=askmn(l[i]-1,i-1);
            ans=max(ans,(R-L)*(LL)a[i]);
        } else
        {
            ans=max(ans,0ll);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

20 − 18 =