1856. 子数组最小乘积的最大值-前准和+单调栈

1856. 子数组最小乘积的最大值-前准和+单调栈

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。
1

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

示例 2：

输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。

示例 3：

输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。

对于这个题目，博主需要强调一点，单调栈可以求解一个数组中，每个数据对应以它为中心，比它大的数据范围，或者比他小的数据范围，另外 famx函数只适用于int 整型数组，解题代码如下：
注：单调栈的这个用法，要记住，以后解题有大用处：

int maxSumMinProduct(int* nums, int numsSize){
    int index_bigger[numsSize];
    int  pre_index_bigger[numsSize];
    int stack[numsSize];
    int index[numsSize];
    int top=0;
    long long presum[numsSize+1];
    presum[0]=0;



    for(int i=0;i<numsSize;i++){
        presum[i+1]=presum[i]+nums[i];
       // printf("%d ",top);
        if(top==0||stack[top-1]<=nums[i]){
            stack[top]=nums[i];
            index[top++]=i;
        }
        else{
            while(stack[top-1]>nums[i]){

            int in=index[top-1];
            index_bigger[in]=i;
            top--;
                if(top==0){
                    break;
                }
            }
            stack[top]=nums[i];
            index[top++]=i;
        }
    }
   // printf("top %d ",top);
    while(top!=0){
        int in=index[top-1];
        index_bigger[in]=numsSize;
        top--;

    }

     for(int i=numsSize-1;i>=0;i--){
       
       // printf("%d ",top);
        if(top==0||stack[top-1]<=nums[i]){
            stack[top]=nums[i];
            index[top++]=i;
        }
        else{
            while(stack[top-1]>nums[i]){

            int in=index[top-1];
            pre_index_bigger[in]=i;
            top--;
                if(top==0){
                    break;
                }
            }
            stack[top]=nums[i];
            index[top++]=i;
        }
    }
   // printf("top %d ",top);
    while(top!=0){
        int in=index[top-1];
        pre_index_bigger[in]=-1;
        top--;

    }
    
  long long max=0;
#define MAX(a, b) ((a) > (b) ? (a) : (b))
   
    for(int i=0;i<numsSize;i++){
      
       

      
        max=MAX(max,(presum[index_bigger[i]]-presum[pre_index_bigger[i]+1])*nums[i]);
        

    }
    

    return max%1000000007;



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88