股票盈利问题(Java)——分治法(Maximum-subarray)

拼搏现实的明天。 2022-05-08 09:14 180阅读 0赞

暴力法解此题:[https://blog.csdn.net/qq\_37486501/article/details/83000154][https_blog.csdn.net_qq_37486501_article_details_83000154]

## 题目 ##

![在这里插入图片描述][70]

*  注意:  
    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 stub
    		long 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 block
    				e.printStackTrace();
    			}
    		} catch (FileNotFoundException e) {
    			// TODO Auto-generated catch block
    			e.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 stub
    		long 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 block
    				e.printStackTrace();
    			}
    		} catch (FileNotFoundException e) {
    			// TODO Auto-generated catch block
    			e.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;
    	}
    }

[https_blog.csdn.net_qq_37486501_article_details_83000154]: https://blog.csdn.net/qq_37486501/article/details/83000154
[70]: /images/20220508/c6a7f3acf3bb45f68741e9a435b2d63c.png