Description

Input

Output

Sample Input

6
3 1 6 4 5 2

Sample Output

60
3 5

Source

给定一序列，求一个子序列要求子序列中的和与子序列中的最小数乘积最大，输出最大乘积以及子序列的起始位置。

我们可以转化为求序列中的每一个数所属于哪个区间，保证该数在这个区间内是最小的，并且这个区间长度最大（比如  3 4 2  6,     2所属区间可以为（4,2）也可以为（4,2,6），我们要求最大的(3,4,2,6)，因为要保证子序列的和最大）。

这样求出每个数的所属区间，比较一下就可以了。传统的求每个数所属区间时间复杂度高O（n2)，可以采用动规的思想，也可以叫回溯，也和KMP的next数组思想有点像

求第i个数所属区间的左端点L[i]时,L[i]肯定小于等于i，所以把i从第i-1个数（i前面的）开始比较，如果第i-1个数比第i个数小，那么肯定L[i] = i+1，第i-1个数小于第i个数，肯定不会在第i个数所属的区间，如果第i-1个数比第i个数大，那么就用第i个数与  L[ i -1] -1 （第i-1个数所属区间左端点的前一个数)进行比较。

求右端点的思想和求左端点的思想是一样的，逆向求。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=100010;
int s[maxn];//存放第i个元素在某个区间内为最小值的区间左端点
int e[maxn];//存放第i个元素在某个区间内为最小值的区间右端点
int node[maxn];//存放输入元素
long long ans;//输出结果
long long sum[maxn];//存放第1到i个元素的和
int S=1,E=1;//输出所求区间的起始位置

int main()
{
    int n;cin>>n;
    sum[0]=0;//以下三行初始化为后面做准备
    node[0]=-1;
    node[n+1]=-1;
    for(int i=1;i<=n;i++)//求第1到i个元素和，并且求出第i个元素所属区间的左端点
    {
        scanf("%d",&node[i]);
        sum[i]=sum[i-1]+node[i];//求和
        for(int j=i-1;j>=0;)//第i个元素从它前面的第一个元素比较
        {
            if(node[i]>node[j])
            {
                s[i]=j+1;//肯定是j+1，因为第j个元素肯定不在第i个元素所属区间内，得保证第i个元素在所属区间内为最小值
                break;
            }
            else
                j=s[j]-1;//回溯，从第j个元素所属区间的前面第一个开始比较，如 1 5 4 2， 2<4,4所属区间为（5,4），s[j]=2,所以与第一个元素1比较
        }
    }
    for(int i=n;i>=1;i--)//逆向求第i个元素所属区间的右端点
    {
        for(int j=i+1;j<=n+1;)//从i后面的第一个元素比较。
        {
            if(node[i]>node[j])//原理同上
            {
                e[i]=j-1;
                break;
            }
            else
                j=e[j]+1;
        }
    }
    long long temp=0;
    ans=-1;
    for(int i=1;i<=n;i++)
    {
        temp=(sum[e[i]]-sum[s[i]-1])*node[i];
        if(temp>ans)
        {
            ans=temp;
            S=s[i];
            E=e[i];
        }
    }
    cout<<ans<<endl;
    cout<<S<<" "<<E<<endl;
    return 0;
}

[ACM] POJ 2796 Feel Good （求序列中子序列的和与子序列中的最小数最大乘积）