编程题2

#include <iostream>
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        int arr[N];
        for (int i=0; i<N; i++)
            scanf("%d",&arr[i]);
        int max=0;
        for (int i=0; i<N; i++)
        {
            int val=0;
            int j=i;
            while(j<N && arr[j]>=arr[i])
            {
                val+=arr[j];
                j++;
            }
            j=i-1;
            while(j>=0 && arr[j]>=arr[i])
            {
                val+=arr[j];
                j--;
            }
            if (arr[i]*val>max)
                max=arr[i]*val;
        }
        printf("%d\n", max);
    }
    return 0;
}

#include<iostream>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    int *array = new int[n];
    for(int i=0; i<n; ++i)
        cin>>array[i];
    int nMax = array[0]*array[0];
    for(int i=0; i<n; ++i)
    {
        int sum = 0;
        int minN = array[i];
        for(int j=i; j<n; ++j)
        {
            if(array[j]==0) break;
            sum += array[j];
            if(minN>array[j])
                minN = array[j];
            if(minN*sum>nMax)
                nMax = minN*sum;
        }
    }
    cout<<nMax;
}
如果缺少if(array[j]==0) break;程序的运行时间是3s，只能通过60%的测试用例。

#include<bits/stdc++.h>
using namespace std;

#define LL long long
const int maxn=5e5+5;

int num[maxn],sum[maxn];
LL result;

void solve(int n)
{
    int left,right;
    for(int i=1;i<=n;++i)
    {
        left=right=i;
        while(num[--left]>=num[i]&&left>0); //寻找左端点
        while(num[++right]>=num[i]&&right<=n); //寻找右端点
        result=max(result,(LL)num[i]*(sum[right-1]-sum[left]));
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&num[i]);
        sum[i]=num[i]+sum[i-1];  //前缀和
    }
    result=0;
    solve(n);
    printf("%lld\n",result);
    return 0;
}

使用单调栈，可以通过全部测试用例

#include 
#include 
#include 
using namespace std;

int findMax(vector v) {
    int len = v.size(), res = 0;
    vector sum(len + 1, 0);
    for (int i = 1; i <= len; ++i) sum[i] = sum[i-1] + v[i-1];
    stack s;
    for (int i = 0; i < len; ++i) {
        while (!s.empty() && v[i] < v[s.top()]) {
            int index = s.top(), left, right = i;
            s.pop();
            if (s.empty()) left = 0;
            else left = s.top() + 1;
            // cout << v[index] * (sum[right] - sum[left]) << endl;
            res = max(res, v[index] * (sum[right] - sum[left]));
        }
        s.push(i);
    }
    while(!s.empty()) {
        int index = s.top(), left, right = len;
        s.pop();
        if (s.empty()) left = 0;
        else left = s.top() + 1;
        // cout << v[index] * (sum[right] - sum[left]) << endl;
        res = max(res, v[index] * (sum[right] - sum[left]));
    }
    return res;
}

int main() {
    // vector v{6,2,5,5,5,4,7};
    int n;
    cin >> n;
    vector v(n);
    for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
    cout << findMax(v) << endl;
}

#第一次求整个数列和乘最小值，以最小值划分成左右两个数组继续求和乘最小值

public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int [] input  =new int [size];
        for(int i=0;i<input.length;i++){
            input[i] = sc.nextInt();
        }

        long max=input[0]*input[0];
        for(int i=0;i<size;i++){
             long sum=input[i];
             int min=input[i];
            for(int j=i+1;j<size;j++){
                if(input[j]==0){
                    break;
                }
                sum+=input[j];
                if(input[j]<min){
                    min = input[j];
                }
                if(min*sum>max){
                    max=min*sum;
                }
            }
        }
        System.out.println(max);
    }

• 直接写，通过，不知道有什么好算法。

if __name__ == "__main__":
    n = int(input())
    inlist = list(map(int,input().split()))

    res = 0
    for i in range(n):
        tmp = inlist[i]
        if tmp == 0:
            continue
        l = r = i
        while l - 1 >= 0 and inlist[l - 1] >= tmp:
            l -= 1
        while r + 1 < n and inlist[r + 1] >= tmp:
            r += 1
        res = max(res, tmp * sum(inlist[l:r + 1]))
    print(res)

遍历每个数，并找出该数的最大区间，即该数在区间中最小，加总求积，已AC

#include <bits/stdc++.h>
using namespace std;
#define nullptr NULL

int main()
{
    freopen("data.in","r", stdin);
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int curMax = a[0] * a[0];
    for(int i = 0; i < n; i++) {
        int curMin = a[i];
        int curSum = 0;
        for(int j = i; j < n; j++) {
            if(a[j] == 0) break;    // 遇到 0, 就 break 
            curSum += a[j];
            if(a[j] < curMin) curMin = a[j];
            int sum = curMin * curSum; 
            if(sum > curMax)
                curMax = sum;
        }
    }

    printf("%d\n", curMax);

    return 0;
}

num = int(input())
list1= (input().split())
for i in range (0,len(list1)):
    list1[i]=int(list1[i])
print (list1)
list2 = []
for j in range (0,num):
     for k in range (j, num):   
            summary = sum(list1[j:k+1])
            list2.append(summary*min(list1[j:k+1]))
print (max(list2))

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int L[1000100];

int main() {
int n;
while(~scanf("%d", &n)) {
int dp[110];
int s = 0;
memset(L, 0, sizeof(L));
memset(dp, 0, sizeof(dp));
for (int i = 0 ; i < n ; i++) {
scanf("%d", &L[i]);
for (int j = 1; j <= 100; j ++) {
if (L[i] >= j) {
dp[j] = dp[j] + j * L[i];
} else {
if (s < dp[j]) {
s = dp[j];
}
dp[j] = 0;
}
}
}
for (int i =1; i <= 100;i ++) {
if (s < dp[i]) {
s = dp[i];
} 
}
printf("%d\n", s);
}
return 0;
}

'''最大区间'''
#以i点为最小值
n = int(input())
nums = list(map(int,input().split()))
res = 0
for i in range(n):
    cur_sum = nums[i]
    #不加超时
    if cur_sum==0:
        continue
    j = i+1
    while j<n and nums[i]<=nums[j]:
        cur_sum += nums[j]
        j += 1
    j = i-1
    while j>=0 and nums[i]<=nums[j]:
        cur_sum += nums[j]
        j -= 1
    res = max(res,cur_sum*nums[i])

print(str(res))

n = int(raw_input())

data_list= [int(x) for x in raw_input().split(' ')]
leng = len(data_list)
result = []
maxflag = 0
data_list = sorted(data_list,reverse=True)

for i in range(leng):
    if i == 0:
        result.append(data_list[0]**2)
    else:
        a = data_list[:i+1]
        result.append(min(a)*sum(a))
print result
print max(result)

python3 通过

import  sys
n = int(sys.stdin.readline().strip())
nums =  list(map(int, sys.stdin.readline().strip().split()))
summax = nums[0] ** 2
for i in range(0,len(nums)):
    if nums[i]==0:#没有这判断python会超时
        continue
    cursum = nums[i]
    l ,r = i-1,i+1
    while l>=0 and nums[l]>=nums[i]:
        cursum +=nums[l]
        l-=1
    while r = nums[i]:
        cursum += nums[r]
        r += 1
    temp = nums[i] * cursum
    if temp > summax:
        summax = temp
print(summax)  

n = int(input())

nums = list(map(int, input().strip().split()))
res = 0
for i in range(n):
    # 取当前值为最小值
    min_ = nums[i]
    sum_ = nums[i]
    res = max(res, nums[i] * nums[i])
    for j in range(i + 1, n):
        # 更新最小值
        min_ = min(min_, nums[j])
        sum_ += nums[j]
        res = max(res, min_*sum_)
print(res)

N = int(input())
a=[int(i) for i in input().split()]
b=a.copy()
a.sort()
M=a[N-1]*a[N-1]
M2=a[0]*sum(a)
if M<M2:
    M=M2
def getmax(x,y):
    global M
    tmp=0
    newlist=[]
    for i in range(y):
        if x+i<N:
            newlist.append(b[x+i])
    newlist.sort()
    tmp=sum(newlist)*newlist[0]
    if tmp>M:
        M=tmp
    if x+y<=N:
        getmax(x+1,y)

for i in range(2,N):
    getmax(0,i)

print(M)