首页 > 试题广场 >

小美的加法

[编程题]小美的加法
  • 热度指数：3832 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美有一个长度为 n 的数组，她想将这个数组进行求和，即 sum = a_1+a_2+...+a_n 。
小美可以使用一次魔法（也可以不使用），将其中一个加号变成乘号，使得 sum 最大。
求出最大的 sum 。

输入描述:
第一行输入一个整数 n 。
第二行输入 n 个整数表示数组 a 。
1 \leq n \leq 10^5
1 \leq a_i \leq 10^9


输出描述:
输出一个整数表示答案。
示例1

输入

6
1 1 4 5 1 4

输出

27

说明

小美可以将 4 和 5 之间的加号改成乘号。
1 + 1 + 4 * 5 + 1 + 4 = 27
算法知识视频讲解
添加回答
不是鸽们儿头像 不是鸽们儿
这个出题人好臭啊！
发表于 2023-08-25 14:13:54 回复(0)
莫盖特笙头像 莫盖特笙
发表于 2023-08-25 11:12:28 回复(0)
牛客825588924号头像 牛客825588924号
题目明显说了，a[i] 是小于10的9次方，但是输入确实大于这个的，题目本身就是错的，美团的技术博客不知道咋来的
发表于 2023-10-14 09:34:02 回复(2)
布鲁诺_头像 布鲁诺_
#include <iostream>
#include<vector>
using namespace std;

int main() {
    /*
        思路：
        朴实无华，就清清爽爽将相邻的两个数的乘积 - 和算出来暂存即可
   
    */

   
    long long num = 0;
    cin >> num;
   

    long long lastNum = 0;
    cin>>lastNum;

    long long sum = lastNum;

    //最大可能增加量
    long long maxAdd = 0;

    long long temp = -1;
    for(long long i = 0; i < num -1; i++)
    {
        cin>>temp;
        sum += temp;

        if( temp * lastNum - temp -lastNum > maxAdd)
        {
            maxAdd = temp*lastNum -temp -lastNum;
        }
       
        lastNum = temp;
    }
    cout<<sum + maxAdd;
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2023-08-31 12:09:24 回复(1)
贝弱得头像 贝弱得
发表于 2023-08-30 10:50:09 回复(1)
Java
木土天王其头像 木土天王其 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        long[] a=new long[n];
        long sum=0;
        long max=1;
        for (int i = 0; i <n ; i++) {
            a[i]=in.nextLong();
            sum+=a[i];
        }
        long r;
        long s=0,b = 0;
        for (int i = 0; i <n-1 ; i++) {
                r=a[i]*a[i+1];
                if (max<=r){
                    max=r;
                    s=a[i];
                    b=a[i+1];
                }
        }
        System.out.println(sum-s-b+max);

    }
}

发表于 2023-08-25 19:37:09 回复(1)
倾城之雨2077头像 倾城之雨2077
为什么不可以先排序只乘最后两个数？
发表于 2023-09-15 21:00:23 回复(4)
长歌行abc头像 长歌行abc
#include <iostream>
#include<vector>
using namespace std;
 
 
intmain() {
    intn;
    cin>>n;
    vector<longlong> vec(n);
    longlongtemp=0;
    intm,z;
    longlongsum=0;
    for(inti=0;i<n;i++){
        cin>>vec[i];
    }
    for(inti=1;i<n;i++){
        longlongsum1=vec[i-1]*vec[i];
        if(sum1>temp){
            temp=sum1;
            m=i-1;z=i;
        }
    }
    sum=temp;
    for(inti=0;i<n;i++){
        if(i!=m&&i!=z){
            sum+=vec[i];
        }
    }
    cout<<sum<<endl;
 
}
发表于 2023-08-23 19:12:54 回复(0)
forriver201908071455331头像 forriver201908071455331
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        Long nums[] = new Long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextLong();
        }
        Long preSum[] = new Long[n + 1];
        preSum[0] = 0l;
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        //
        Long ans = Long.MIN_VALUE;
        //求和
        Long tempSum = 0l;

        for (int k = 0; k < nums.length - 1; k++) {
            if (k == 0)
                tempSum = nums[k] * nums[k + 1] + preSum[nums.length] - preSum[k + 2];
            else if (k == 1) {
                tempSum = nums[k] * nums[k + 1] + preSum[nums.length] - preSum[k + 2] + nums[1];
            } else {
                tempSum = nums[k] * nums[k + 1] + preSum[nums.length] - preSum[k + 2] + preSum[k] - preSum[0];
            }
            ans = Math.max(tempSum, ans);
        }

        System.out.println(ans);
    }
}

发表于 2023-08-25 13:32:25 回复(0)
牛客933757666号头像 牛客933757666号
还要考虑因为数字太大失真？有没有前端的标准答案？
编辑于 2024-02-04 16:04:54 回复(3)
Java
青春猪头少年不会没有offer头像 青春猪头少年不会没有offer 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] a = new long[n];
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextLong();
            sum += a[i];
        }
        long ans = sum;
        for (int i = 0; i < n - 1; ++i) {
            ans = Math.max(ans, sum - a[i] - a[i + 1] + a[i] * a[i + 1]);
        }
        System.out.println(ans);
    }
}

编辑于 2023-12-26 20:41:47 回复(1)
烤串不吃串头像 烤串不吃串
直接计算改变当前符号的增量，取最大的增量即可。 

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();
        long[] nums = new long[a];
        long res = 0;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            for (int i = 0; i < a; i++) {
                nums[i] = in.nextInt();
                // nums[i] *= nums[i];
                res += nums[i];
            }
        }
        long value = 0;
        for (int i = 0; i < a-1; i++) {
            long temp = nums[i] * nums[i+1] - nums[i] - nums[i+1];
            if (temp > value) {
                value = temp;
            }
        }
        System.out.println(res + value);
        return ;
    }
}


编辑于 2023-12-26 18:46:43 回复(0)
mrk666头像 mrk666
要什么动态规划，直接，比较找最大的相邻两数乘积就行 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            String[] strArr = in.nextLine().split(" ");
            long[] arr = new long[n];
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(strArr[i]);
            }
            long max=0;
            long subSum=0;
            long sum=arr[0];
            for(int i=1; i<n; i++){
                long pre = arr[i-1];
                long cur = arr[i];
                if(max<pre*cur){
                    max = pre*cur;
                    subSum=pre+cur;
                }
                sum+=cur;
            }
            System.out.println(sum-subSum+max);
        }
    }
}


发表于 2023-12-14 18:11:16 回复(0)
低调的泡椒凤爪头像 低调的泡椒凤爪
n= int(input())
s = list(map(int,input().split()))
 
res = sum(s)
final= 0
 
i, j = 0,1
fori in range(n-2):
    mul = s[i] * s[i+1]
    temp = res - s[i] - s[i+1] + mul
    final= max(final, temp)
     
 
print(final)
 
 
发表于 2023-11-26 00:13:09 回复(0)
Java
卖到了一袋米头像 卖到了一袋米 
import java.util.Scanner;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Long> list = new ArrayList<>();
        long first;
        long next = 1;
        long mult;
        long mult1 = 0;
        long sub = 0;
        long sub1 = 0;
        long sum = 0;
        boolean b =false;
        while (scanner.hasNextLong()){
            long math = scanner.nextLong();
            for (int i = 0; i < math; i++) {
                first = scanner.nextInt();
                list.add(first);
                mult = first * next;
                if (sub1 == 0){
                    if (mult > mult1 && mult > first + next - 1){
                        mult1 = mult;
                        sub1 = sub;
                        b =true;
                    }
                }else  if (mult > mult1 && mult > first + next){
                    mult1 = mult;
                    sub1 = sub;
                    b =true;
                }
                next = first;
                sub++;
            }

        }
        for (int i = 0; i < list.size(); i++) {
            if ((i == sub1 - 1 || i == sub1) && b == true ){
                continue;
            }
            sum = sum + list.get(i);
        }
        sum = sum + mult1;
        System.out.println(sum);
    }
}


我的答案看来复杂得多啊
发表于 2023-11-19 22:12:14 回复(0)
Java
牛客659335030号头像 牛客659335030号 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class TestNiuKeMain2 {
    public static void main(String[] args) {
        System.out.println(Long.MAX_VALUE);
        System.out.println("===== test1 =====");
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        System.out.println(count);
        long sum = 0;
        long[] nums = new long[count];
        for (int i = 0; i < count; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }
        long res = 0;
        for (int i = 1; i < count; i++) {
            res = Math.max(res, sum - nums[i] - nums[i - 1] + nums[i] * nums[i - 1]);
        }
        System.out.println(res);
    }
}

发表于 2023-10-09 13:15:50 回复(0)
余get水头像 余get水 
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const count = await readline()
    // Write your code here
    while(line = await readline()){
        let tokens = line.split(' ').map(Number);
        tokens.sort()
        const max = tokens.pop() * tokens.pop()
        const result = tokens.reduce((pre,current)=> pre+current,max)
        console.log(result);
    }
}()
哪里有问题呢

发表于 2023-10-07 17:29:23 回复(0)
Python
G了的伊登很胖墩墩头像 G了的伊登很胖墩墩
n = int(input())
 
number =list(int(x) forx in input().split())
 
old_sum= sum(number)
 
test = 0
flag = 0
fori in range(n-1):
    mid = number[i] * number[i+1]
    ifmid>test:
        test = mid
        flag = i
 
new_sum = old_sum - (number[flag] + number[flag+1]) + (number[flag] * number[flag+1])
 
print(max(old_sum,new_sum))
发表于 2023-09-14 18:37:10 回复(0)
Java
sinare_merlori头像 sinare_merlori 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        long[] arr = new long[length];
        for(int i=0 ;i<length;i++){
            arr[i] = in.nextLong();
        }
        long gap = 0;
        int left =0;int right = 1;
        while(right < length){
            gap = Math.max(gap,arr[left]*arr[right] - (arr[left]+arr[right]));
            left++;right++;
        }
        long sum = Arrays.stream(arr).sum();
        sum = Math.max(sum,sum+gap);
        System.out.println(sum);
    }
}

简单明了看了都说好
编辑于 2023-09-12 11:29:13 回复(0)
wdyjwdy头像 wdyjwdy 
offset = 0
for i in range(0, n - 1):
    tmp = a[i]*a[i+1] - (a[i]+a[i+1])
    if tmp > offset:
        offset = tmp
out = sum(a) + offset
print(out)
发表于 2023-09-08 14:43:15 回复(0)
提交观点

问题信息

来自：美团2023年秋招笔试...
难度：
27条回答 2827浏览

热门推荐

相关试题

小美的加法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号