假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票,并非每天都可以买入或卖出一次,总共只能买入和卖出一次,且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润,请返回0
3.假设买入卖出均无手续费
数据范围:
第一行输入一个正整数 n 表示数组的长度第二行输入 n 个正整数,表示股票在第 i 天的价格
输出只买卖一次的最高收益
7 8 9 2 5 4 7 1
5
在第3天(股票价格 = 2)的时候买入,在第6天(股票价格 = 7)的时候卖出,最大利润 = 7-2 = 5 ,不能选择在第2天买入,第3天卖出,这样就亏损7了;同时,你也不能在买入前卖出股票。
3 2 4 1
2
3 3 2 1
0
int max_profit(int prices[], int size) { int i, n = 0, m = 0; for (int i = 1; i < size; i++) { //若是一直有利润,意味着买的那一天价钱最低 if (prices[i] - prices[n] <= 0) { n = i;//无利润代表下标为i的元素比先前的购入价便宜,所以从该元素开始买股票 } else { m = max(m, prices[i] - prices[n]);//存储最大的利润值 } } return m; }
简单贪心
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int p[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) cin >> p[i]; int ans = 0, mi = 1e5; for(int i = 0; i < n; i++) { ans = max(ans, p[i] - mi); mi = min(mi, p[i]); } cout << ans << '\n'; }
import sys def main(): n = int(sys.stdin.readline().strip()) arr = list(map(int, sys.stdin.readline().strip().split(' '))) dp = [0 for i in range(n)] dp[0] = arr[0] # 从左边顺延遇到的最小的值 for i in range(1, n): if arr[i] > dp[i-1]: dp[i] = dp[i-1] else: dp[i] = arr[i] # print(dp) # 计算从右边减去左边最小的值 res = 0 for i in range(n-1, -1, -1): res = max(res, arr[i] - dp[i]) print(res) main()
import java.util.*; public class Main{ public static void main(String[] args){ //处理输入输出 Scanner scan=new Scanner(System.in); String nStr=scan.nextLine();//输入一个正整数n 读取第一行数据 int n=Integer.valueOf(nStr);//将String变int String numsStr=scan.nextLine();//输出n个正整数 读取第二行数据 String[] numsStrList=numsStr.split(" "); int[] nums=new int[numsStrList.length]; for(int i=0;i<nums.length;i++){ //String[]变int[] nums[i]=Integer.valueOf(numsStrList[i]); } //核心代码模式 //if(nums==null||nums.length==0) { if(nums.length==1){ System.out.println(0); return; } int[][] dp=new int[nums.length][2]; //0表示持有 1表示不持有 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],-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]) ; } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static StreamTokenizer st; public static void main(String[] args) throws IOException { st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int n = nextInt(); int[] arr = new int[n]; for(int i = 0;i < n;i++) { arr[i] = nextInt(); } int min = Integer.MAX_VALUE,max = 0; for(int i = 0;i < n;i++) { if(arr[i] < min) {//判断当前价格是否相对前面较低 min = arr[i]; }else if(arr[i] - min > max) {//判断当前卖出是否最赚 max = arr[i] - min; } } System.out.println(max); } public static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } }
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],-arr[i]); } System.out.println(dp[n-1][0]); } }
#include<iostream> using namespace std; int main(){ int n,today,lowest=0x3f3f3f3f,result=0; cin>>n; for(int i=1;i<=n;i++){ cin>>today; result=max(result,today-lowest); lowest=min(lowest,today); } cout<<result<<endl; }
fun main(){ //dp(i) = Max(dp(i-1) + price[i-1] - price[i-2], price[i-1]-price[i-2]) //max(n) = max(dp(2) .. dp(n)) var maxSubSum = 0; var n = readLine()!!.toInt(); var strArray = readLine()!!.split(" "); var intArray = IntArray(size = n , init = { it -> strArray[it].toInt() }) var dp = IntArray(size = n+2, init = { -200000 }) var begin=-1 var end=-1 dp[1] = 0 if(n >= 2){ for(i in 2 .. intArray.size){ if(dp[i-1] + intArray[i-1] - intArray[i-2] > intArray[i-1] - intArray[i-2] ) { dp[i] = dp[i-1] + intArray[i-1] - intArray[i-2]; end = i; } else { dp[i] = intArray[i-1] - intArray[i-2] ; begin=i-2; end = i-1; } } } for(dpValue in dp){ if(maxSubSum < dpValue){ maxSubSum = dpValue; } } //println( "begin=${begin} end=${end}" ); println(maxSubSum); }
#include<bits/stdc++.h> using namespace std; int maxProfit(vector<int>&prices){ int n=prices.size(); //dp[i]表示第i天获得的最大利润 vector<int>dp(n); dp[0]=0; int minPrice=prices[0]; for(int i=1;i<n;i++){ minPrice=min(minPrice,prices[i]); //两种状态:今天不卖,今天卖 dp[i]=max(dp[i-1],prices[i]-minPrice); } return dp[n-1]; } int main(){ int n;cin>>n; vector<int>Prices(n); for(int i=0;i<n;i++) cin>>Prices[i]; cout<<maxProfit(Prices); }