算法訓練 最大的算式 時間限制：1.0s 內(nèi)存限制：256.0MB問題描述題目很簡單，給出N個數(shù)字，不改變它們的相對位置，在中間加入K個乘號和N-K-1個加號，（括號隨便加）使最終結果盡量大。因為乘號和加號一共就是N-1個了，所以恰好每兩個相鄰數(shù)字之間都有一個符號。例如：N=5，K=2，5個數(shù)字分別為1、2、3、4、5，可以加成：1*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45……輸入格式輸入文件共有二行，第一行為兩個有空格隔開的整數(shù)，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行為 N個用空格隔開的數(shù)字（每個數(shù)字在0到9之間）。輸出格式輸出文件僅一行包含一個整數(shù)，表示要求的最大的結果樣例輸入5 21 2 3 4 5樣例輸出120樣例說明(1+2+3)*4*5=120

解題思路：使用了動態(tài)規(guī)劃和遞歸的思想。

package com.sihai.advance;import java.util.Scanner;public class Main{//求取數(shù)組A[start]到A[end]之間元素總和public long getSum(int[] A, int start, int end) {long sum = 0;for(int i = start;i <= end;i++)sum += A[i];return sum;}/** 參數(shù)start：數(shù)組A中開始劃分元素的起始位置* 參數(shù)multi:進行乘法運算的個數(shù)*/public long getMax(int[] A, int start, int multi) {if(multi == 0)return getSum(A, start, A.length - 1);long max = 0;for(int i = start;i < A.length - 1;i++) { //此處i < A.length - 1原因是遞歸時start = i + 1，且start要小于等于A.length - 1long tempMax = getSum(A, start, i) * getMax(A, i + 1, multi - 1);max = (max < tempMax ? tempMax : max);}return max;}public static void main(String[] args){Main test = new Main(); Scanner in = new Scanner(System.in);// System.out.println("請分別輸入一個整數(shù)n和一個整數(shù)k：");int n = in.nextInt();int k = in.nextInt();int[] A = new int[n];for(int i = 0;i < n;i++)A[i] = in.nextInt();System.out.println(test.getMax(A, 0, k));} }

總結

以上是生活随笔為你收集整理的蓝桥杯-最大的算式（java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。