假设你有一个数组prices,长度为n,其中prices[i]是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1. 你可以多次买卖该只股票,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费
数据范围: ,
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
第一行输入一个正整数 n ,表示数组 prices 的长度第二行输入 n 个正整数,表示数组中prices的值
输出最大收益
7 8 9 2 5 4 7 1
7
在第1天(股票价格=8)买入,第2天(股票价格=9)卖出,获利9-8=1
在第3天(股票价格=2)买入,第4天(股票价格=5)卖出,获利5-2=3
在第5天(股票价格=4)买入,第6天(股票价格=7)卖出,获利7-4=3
总获利1+3+3=7,返回7
5 5 4 3 2 1
0
由于每天股票都在跌,因此不进行任何交易最优。最大收益为0。
5 1 2 3 4 5
4
第一天买进,最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。
// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); String str1=scan.nextLine(); int n=Integer.valueOf(str1); String str2=scan.nextLine(); String[] str3=str2.split(" "); int[] nums=new int[str3.length]; for(int i=0;i<nums.length;i++){ nums[i]=Integer.valueOf(str3[i]); } // if(nums.length==1){ System.out.println(0); return; } int[][] dp=new int[nums.length][2]; dp[0][0]=-nums[0]; dp[0][1]=0; for(int i=1;i<nums.length;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-nums[i]); dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+nums[i]); } System.out.println(dp[nums.length-1][1]); } }
package main import ( "fmt" ) func main() { var n int fmt.Scan(&n) var x int fmt.Scan(&x) pre:=make([]int,2) pre[0]=-x pre[1]=0 for n>1{ fmt.Scan(&x) cur:=make([]int,2) cur[0]=max(pre[0],pre[1]-x) cur[1]=max(pre[1],pre[0]+x) pre=cur n-- } fmt.Print(pre[1]) } func max(a,b int)int{ if a>b{ return a } return b }
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 n=in.nextInt(); int[] arr=new int[n]; int[][] dp=new int[n+1][2]; for(int i=0;i<n;i++) arr[i]=in.nextInt(); dp[0][1]=-arr[0]; for(int i=1;i<n;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+arr[i]); dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-arr[i]); } System.out.println(dp[n-1][0]); } }
#include<iostream> using namespace std; int main(){ int n; cin>>n; int yestoday,res=0; cin>>yestoday; for(int i=1;i<n;i++){ int today,gain; cin>>today; gain=today-yestoday; if(gain>0){ res+=gain; } yestoday=today; } cout<<res<<endl; }
#include<bits/stdc++.h> using namespace std; int maxProfit(vector<int>&prices){ int n=prices.size(); vector<vector<int>>dp(n,vector<int>(2)); //dp[i][0]表示第i天手头没有股票,前一天可进行的操作:卖出一只,或不操作 //dp[i][1]表示第i天手头有一只股票,前一天可进行的操作:买入一只,或不操作 dp[0][0]=0; dp[0][1]=-prices[0]; for(int i=1;i<n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]); } return dp[n-1][0]; } int main(){ int n;cin>>n; vector<int>prices(n); for(int i=0;i<n;i++) cin>>prices[i]; cout<<maxProfit(prices); }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] prices = new int[n]; for ( int i=0;i<n;i++){ prices[i] = sc.nextInt(); } int[][] dp = new int[n][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for ( int i=1;i<n;i++){ dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]); dp[i][1] = Math.max(dp[i-1][0]+prices[i],dp[i-1][1]); } System.out.println(dp[n-1][1]); } }