Java实现 蓝桥杯 算式最大值

算式最大值

【问题描述】

给定:

1)N个正整数A1, A2, … AN;

2)P个加号+和Q个减号-; (P+Q=N-1)

3)K对括号()

请你使用全部整数、加减号和括号，组成一个合法的算式(A1~AN在算式中的顺序随意)，使得算式的结果最大。

注意加减号只能作为二元运算符出现在算式中，不能作为正负号。

括号可以出现在算式最左和最右，例如(((1+2)))是合法的。

例如对于样例数据，(2-1)+3或3+(2-1)等都是结果最大的算式。

【输入】

第一行包含4个整数，N，P, Q和K。

第二行包含N个整数A1, A2, … AN。

2 ≤ N ≤ 100 P+Q+1=N 0 ≤ K ≤ 10

1 ≤ Ai ≤ 1000

【输出】

最大算式结果

【样例输入】

3 1 1 1

1 2 3

【样例输出】

4

PS：

这是一道思维题 只要有括号总能把若干个减号化成一个减号 我们只要减去数组里最小的即可；

举例：4,3,2,1 ：2个减号 1个加号 一个括号 最大为：4-（1-2）+3 两个减号 一个加号 两个括号时：（4-（1-2））+3

三个减号 一个括号：4-（1-2-3） 两个括号时：（4-（1-2-3））

所以有括号时直接是排序 用除了第一项的和减去最小的；

没括号是加号个数加1大的数减去剩下的 具体看代码：

import java.util.Arrays;

import java.util.Scanner;

public class Demo7最大的算是 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int p=sc.nextInt();

		int q=sc.nextInt();

		int k=sc.nextInt();

		int [] a = new int [n+1];

		for (int i = 1; i <=n; i++) {

			a[i]=sc.nextInt();

		}

		sc.close();

		int ans=0;

		Arrays.sort(a);

		if(q==0){

			for(int i=n;i>=1;i--)

				ans+=a[i];

		}

		else if(k==0){

			for(int i=n;i>=1;i--){

				if(i-p-1>=0) ans+=a[i];

				else ans-=a[i];

			}

		}

		else{

			for(int i=n;i>1;i--) ans+=a[i];

			ans-=a[1];

		}

		System.out.println(ans);

	}

}