暴力法解此题:https://blog.csdn.net/qq_37486501/article/details/83000154
题目
-
注意:
1.本题采用txt文件读入,屏幕输出;
如果需要屏幕读入屏幕输出,可以留言或者自己改代码~
2.下面分int类型和double类型的数据读入,请选择适合自己的… -
分治法(Maximum-subarray)代码如下:
要求(输入数据为int类型)
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
class Pro{private int i=0;//买入股票下标private int j=0;//卖出股票下标private int sum=0;//所加和private int k=0;public int getI() {return i;}public void setI(int i) {this.i = i;}public int getJ() {return j;}public void setJ(int j) {this.j = j;}public int getSum() {return sum;}public void setSum(int k) {this.sum =this.sum+k;}
}public class Lyx {public static void main(String[] args) {// TODO Auto-generated method stublong startTime = System.currentTimeMillis();try {FileReader in = new FileReader("input.txt");BufferedReader inin=new BufferedReader(in);//读入文件try {String str; int i=0;int sum=Integer.parseInt(inin.readLine());int[] datalist=new int[sum];while((str=inin.readLine())!=null)//每次读一行,注意双层括号{ datalist[i]=Integer.parseInt(str);i++;}int[] list=new int[sum];for(int m=1;m<sum;m++){list[m]=datalist[m]-datalist[m-1];//list[ ]为股票( 后一天 - 前一天 )//System.out.print(list[m]+" ");} System.out.println("Maximum-subarray求解:");System.out.println("第"+(FindMaxSubarray(list,1,sum-1).getI()-1)+"日收盤買進第"+FindMaxSubarray(list,1,sum-1).getJ()+"日收盤賣出最高獲利為"+FindMaxSubarray(list,1,sum-1).getSum()+"元!");//求最大利润} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}} catch (FileNotFoundException e) {// TODO Auto-generated catch blocke.printStackTrace();}//计算时间long endTime = System.currentTimeMillis();System.out.print("执行时间： "+(endTime-startTime)+" ms"); }public static Pro FindMaxSubarray (int[] data, int low,int high) { int mid;Pro leftsum=new Pro();Pro rightsum=new Pro();Pro midsum=new Pro();if(high==low){ Pro pro1=new Pro();pro1.setI(low);pro1.setJ(high);pro1.setSum(data[high]);}else{ mid = (low+high)/2; leftsum=FindMaxSubarray(data,low,mid);rightsum=FindMaxSubarray(data,mid+1,high);midsum=FindMaxCrossingSubarray(data,low,mid,high);}if((leftsum.getSum()>=rightsum.getSum())&&(leftsum.getSum()>=midsum.getSum())){return leftsum;}else if((rightsum.getSum()>=leftsum.getSum())&&(rightsum.getSum()>=midsum.getSum())){return rightsum;}else if((midsum.getSum()>=leftsum.getSum())&&(midsum.getSum()>=rightsum.getSum())){return midsum;} return null; }public static Pro FindMaxCrossingSubarray (int[] data, int low,int mid,int high) {//以中间开始,向左边求sum1的max,向右边求sum2的max,两个max相加//左侧Pro pro1=new Pro();int leftsum=-1000;int sum1=0;//左侧各项相加的和int maxleftid=0;//左侧max时的i值for(int i=mid;i>=low;i--){sum1=sum1+data[i];if(sum1>leftsum){leftsum=sum1;maxleftid=i; }}pro1.setSum(leftsum);pro1.setI(maxleftid);//右侧int rightsum=-1000;int sum2=0;//右侧各项相加的和int maxrightid=0;//右侧max时的i值for(int i=mid+1;i<=high;i++){sum2=sum2+data[i];if(sum2>rightsum){rightsum=sum2;maxrightid=i; }}pro1.setSum(rightsum);pro1.setJ(maxrightid);return pro1;}
}
- 分治法(Maximum-subarray)代码如下:
要求(输入数据为double类型)
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
class Pro{private int i=0;//买入股票下标private int j=0;//卖出股票下标private double sum=0;//所加和private double k=0;public int getI() {return i;}public void setI(int i) {this.i = i;}public int getJ() {return j;}public void setJ(int j) {this.j = j;}public double getSum() {return sum;}public double setSum(double k) {return this.sum =this.sum+k;}
}public class Lyx {public static void main(String[] args) {// TODO Auto-generated method stublong startTime = System.currentTimeMillis();try {FileReader in = new FileReader("input_2330.txt");BufferedReader inin=new BufferedReader(in);//读入文件try {String str; int i=0;int sum=Integer.parseInt(inin.readLine());double[] datalist=new double[sum];while((str=inin.readLine())!=null)//每次读一行,注意双层括号{ datalist[i]=Double.parseDouble(str);i++;}double[] list=new double[sum];for(int m=1;m<sum;m++){list[m]=datalist[m]-datalist[m-1];//list[ ]为股票( 后一天 - 前一天 )//System.out.print(list[m]+" ");} System.out.println("Maximum-subarray求解:");System.out.println("第"+(FindMaxSubarray(list,1,sum-1).getI()-1)+"日收盤買進第"+FindMaxSubarray(list,1,sum-1).getJ()+"日收盤賣出最高獲利為"+FindMaxSubarray(list,1,sum-1).getSum()+"元!");//求最大利润} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}} catch (FileNotFoundException e) {// TODO Auto-generated catch blocke.printStackTrace();}//计算时间long endTime = System.currentTimeMillis();System.out.print("执行时间： "+(endTime-startTime)+" ms"); }public static Pro FindMaxSubarray (double[] data, int low,int high) { int mid;Pro leftsum=new Pro();Pro rightsum=new Pro();Pro midsum=new Pro();if(high==low){ Pro pro1=new Pro();pro1.setI(low);pro1.setJ(high);pro1.setSum(data[high]);}else{ mid = (low+high)/2; leftsum=FindMaxSubarray(data,low,mid);rightsum=FindMaxSubarray(data,mid+1,high);midsum=FindMaxCrossingSubarray(data,low,mid,high);}if((leftsum.getSum()>=rightsum.getSum())&&(leftsum.getSum()>=midsum.getSum())){return leftsum;}else if((rightsum.getSum()>=leftsum.getSum())&&(rightsum.getSum()>=midsum.getSum())){return rightsum;}else if((midsum.getSum()>=leftsum.getSum())&&(midsum.getSum()>=rightsum.getSum())){return midsum;} return null; }public static Pro FindMaxCrossingSubarray (double[] data, int low,int mid,int high) {//以中间开始,向左边求sum1的max,向右边求sum2的max,两个max相加//左侧Pro pro1=new Pro();double leftsum=-1000;double sum1=0;//左侧各项相加的和int maxleftid=0;//左侧max时的i值for(int i=mid;i>=low;i--){sum1=sum1+data[i];if(sum1>leftsum){leftsum=sum1;maxleftid=i; }}pro1.setSum(leftsum);pro1.setI(maxleftid);//右侧double rightsum=-1000;double sum2=0;//右侧各项相加的和int maxrightid=0;//右侧max时的i值for(int i=mid+1;i<=high;i++){sum2=sum2+data[i];if(sum2>rightsum){rightsum=sum2;maxrightid=i; }}pro1.setSum(rightsum);pro1.setJ(maxrightid);return pro1;}
}