一只股票每天的成本以一个数组的形式给出，找出你在那几天通过买卖可以获得的最大利润。例如，如果给定的数组是{100、180、260、310、40、535、695}，那么在第0天买入，在第3天卖出，就可以获得最大利润。第4天再次买入，第6天卖出。如果给定的价格数组按降序排序，则根本无法赚取利润。
null
天真的方法： 一个简单的方法是尝试在每天盈利的时候买入并卖出股票，并不断更新迄今为止的最大利润。
以下是上述方法的实施情况：
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum profit // that can be made after buying and // selling the given stocks int maxProfit( int price[], int start, int end) { // If the stocks can't be bought if (end <= start) return 0; // Initialise the profit int profit = 0; // The day at which the stock // must be bought for ( int i = start; i < end; i++) { // The day at which the // stock must be sold for ( int j = i + 1; j <= end; j++) { // If buying the stock at ith day and // selling it at jth day is profitable if (price[j] > price[i]) { // Update the current profit int curr_profit = price[j] - price[i] + maxProfit(price, start, i - 1) + maxProfit(price, j + 1, end); // Update the maximum profit so far profit = max(profit, curr_profit); } } } return profit; } // Driver code int main() { int price[] = { 100, 180, 260, 310, 40, 535, 695 }; int n = sizeof (price) / sizeof (price[0]); cout << maxProfit(price, 0, n - 1); return 0; } |
JAVA
// Java implementation of the approach import java.util.*; class GFG { // Function to return the maximum profit // that can be made after buying and // selling the given stocks static int maxProfit( int price[], int start, int end) { // If the stocks can't be bought if (end <= start) return 0 ; // Initialise the profit int profit = 0 ; // The day at which the stock // must be bought for ( int i = start; i < end; i++) { // The day at which the // stock must be sold for ( int j = i + 1 ; j <= end; j++) { // If buying the stock at ith day and // selling it at jth day is profitable if (price[j] > price[i]) { // Update the current profit int curr_profit = price[j] - price[i] + maxProfit(price, start, i - 1 ) + maxProfit(price, j + 1 , end); // Update the maximum profit so far profit = Math.max(profit, curr_profit); } } } return profit; } // Driver code public static void main(String[] args) { int price[] = { 100 , 180 , 260 , 310 , 40 , 535 , 695 }; int n = price.length; System.out.print(maxProfit(price, 0 , n - 1 )); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach # Function to return the maximum profit # that can be made after buying and # selling the given stocks def maxProfit(price, start, end): # If the stocks can't be bought if (end < = start): return 0 ; # Initialise the profit profit = 0 ; # The day at which the stock # must be bought for i in range (start, end, 1 ): # The day at which the # stock must be sold for j in range (i + 1 , end + 1 ): # If buying the stock at ith day and # selling it at jth day is profitable if (price[j] > price[i]): # Update the current profit curr_profit = price[j] - price[i] + maxProfit(price, start, i - 1 ) + maxProfit(price, j + 1 , end); # Update the maximum profit so far profit = max (profit, curr_profit); return profit; # Driver code if __name__ = = '__main__' : price = [ 100 , 180 , 260 , 310 , 40 , 535 , 695 ]; n = len (price); print (maxProfit(price, 0 , n - 1 )); # This code is contributed by Rajput-Ji |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum profit // that can be made after buying and // selling the given stocks static int maxProfit( int []price, int start, int end) { // If the stocks can't be bought if (end <= start) return 0; // Initialise the profit int profit = 0; // The day at which the stock // must be bought for ( int i = start; i < end; i++) { // The day at which the // stock must be sold for ( int j = i + 1; j <= end; j++) { // If buying the stock at ith day and // selling it at jth day is profitable if (price[j] > price[i]) { // Update the current profit int curr_profit = price[j] - price[i] + maxProfit(price, start, i - 1) + maxProfit(price, j + 1, end); // Update the maximum profit so far profit = Math.Max(profit, curr_profit); } } } return profit; } // Driver code public static void Main(String[] args) { int []price = { 100, 180, 260, 310, 40, 535, 695 }; int n = price.Length; Console.Write(maxProfit(price, 0, n - 1)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum profit // that can be made after buying and // selling the given stocks function maxProfit( price, start, end) { // If the stocks can't be bought if (end <= start) return 0; // Initialise the profit let profit = 0; // The day at which the stock // must be bought for (let i = start; i < end; i++) { // The day at which the // stock must be sold for (let j = i + 1; j <= end; j++) { // If buying the stock at ith day and // selling it at jth day is profitable if (price[j] > price[i]) { // Update the current profit let curr_profit = price[j] - price[i] + maxProfit(price, start, i - 1) + maxProfit(price, j + 1, end); // Update the maximum profit so far profit = Math.max(profit, curr_profit); } } } return profit; } // Driver program let price = [ 100, 180, 260, 310, 40, 535, 695 ]; let n = price.length; document.write(maxProfit(price, 0, n - 1)); </script> |
输出
865
有效方法： 如果我们只允许买卖一次，那么我们可以使用以下算法。 两个元素之间的最大差值 .在这里我们可以多次买卖。 下面是这个问题的算法。
- 找到局部极小值并将其存储为起始索引。如果不存在，请返回。
- 找到局部最大值。并将其存储为结束索引。如果我们到达终点，将终点设置为终点索引。
- 更新解决方案（买卖对的增量计数）
- 如果未到达终点，重复上述步骤。
C++
// C++ Program to find best buying and selling days #include <bits/stdc++.h> using namespace std; // This function finds the buy sell // schedule for maximum profit void stockBuySell( int price[], int n) { // Prices must be given for at least two days if (n == 1) return ; // Traverse through given price array int i = 0; while (i < n - 1) { // Find Local Minima // Note that the limit is (n-2) as we are // comparing present element to the next element while ((i < n - 1) && (price[i + 1] <= price[i])) i++; // If we reached the end, break // as no further solution possible if (i == n - 1) break ; // Store the index of minima int buy = i++; // Find Local Maxima // Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i - 1])) i++; // Store the index of maxima int sell = i - 1; cout << "Buy on day: " << buy << " Sell on day: " << sell << endl; } } // Driver code int main() { // Stock prices on consecutive days int price[] = { 100, 180, 260, 310, 40, 535, 695 }; int n = sizeof (price) / sizeof (price[0]); // Function call stockBuySell(price, n); return 0; } // This is code is contributed by rathbhupendra |
C
// Program to find best buying and selling days #include <stdio.h> // solution structure struct Interval { int buy; int sell; }; // This function finds the buy sell schedule for maximum profit void stockBuySell( int price[], int n) { // Prices must be given for at least two days if (n == 1) return ; int count = 0; // count of solution pairs // solution vector Interval sol[n / 2 + 1]; // Traverse through given price array int i = 0; while (i < n - 1) { // Find Local Minima. Note that the limit is (n-2) as we are // comparing present element to the next element. while ((i < n - 1) && (price[i + 1] <= price[i])) i++; // If we reached the end, break as no further solution possible if (i == n - 1) break ; // Store the index of minima sol[count].buy = i++; // Find Local Maxima. Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i - 1])) i++; // Store the index of maxima sol[count].sell = i - 1; // Increment count of buy/sell pairs count++; } // print solution if (count == 0) printf ( "There is no day when buying the stock will make profitn" ); else { for ( int i = 0; i < count; i++) printf ( "Buy on day: %dt Sell on day: %dn" , sol[i].buy, sol[i].sell); } return ; } // Driver program to test above functions int main() { // stock prices on consecutive days int price[] = { 100, 180, 260, 310, 40, 535, 695 }; int n = sizeof (price) / sizeof (price[0]); // function call stockBuySell(price, n); return 0; } |
JAVA
// Program to find best buying and selling days import java.util.ArrayList; // Solution structure class Interval { int buy, sell; } class StockBuySell { // This function finds the buy sell schedule for maximum profit void stockBuySell( int price[], int n) { // Prices must be given for at least two days if (n == 1 ) return ; int count = 0 ; // solution array ArrayList<Interval> sol = new ArrayList<Interval>(); // Traverse through given price array int i = 0 ; while (i < n - 1 ) { // Find Local Minima. Note that the limit is (n-2) as we are // comparing present element to the next element. while ((i < n - 1 ) && (price[i + 1 ] <= price[i])) i++; // If we reached the end, break as no further solution possible if (i == n - 1 ) break ; Interval e = new Interval(); e.buy = i++; // Store the index of minima // Find Local Maxima. Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i - 1 ])) i++; // Store the index of maxima e.sell = i - 1 ; sol.add(e); // Increment number of buy/sell count++; } // print solution if (count == 0 ) System.out.println( "There is no day when buying the stock " + "will make profit" ); else for ( int j = 0 ; j < count; j++) System.out.println( "Buy on day: " + sol.get(j).buy + " " + "Sell on day : " + sol.get(j).sell); return ; } public static void main(String args[]) { StockBuySell stock = new StockBuySell(); // stock prices on consecutive days int price[] = { 100 , 180 , 260 , 310 , 40 , 535 , 695 }; int n = price.length; // function call stock.stockBuySell(price, n); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 Program to find # best buying and selling days # This function finds the buy sell # schedule for maximum profit def stockBuySell(price, n): # Prices must be given for at least two days if (n = = 1 ): return # Traverse through given price array i = 0 while (i < (n - 1 )): # Find Local Minima # Note that the limit is (n-2) as we are # comparing present element to the next element while ((i < (n - 1 )) and (price[i + 1 ] < = price[i])): i + = 1 # If we reached the end, break # as no further solution possible if (i = = n - 1 ): break # Store the index of minima buy = i i + = 1 # Find Local Maxima # Note that the limit is (n-1) as we are # comparing to previous element while ((i < n) and (price[i] > = price[i - 1 ])): i + = 1 # Store the index of maxima sell = i - 1 print ( "Buy on day: " ,buy, " " , "Sell on day: " ,sell) # Driver code # Stock prices on consecutive days price = [ 100 , 180 , 260 , 310 , 40 , 535 , 695 ] n = len (price) # Function call stockBuySell(price, n) # This is code contributed by SHUBHAMSINGH10 |
C#
// C# program to find best buying and selling days using System; using System.Collections.Generic; // Solution structure class Interval { public int buy, sell; } public class StockBuySell { // This function finds the buy sell // schedule for maximum profit void stockBuySell( int []price, int n) { // Prices must be given for at least two days if (n == 1) return ; int count = 0; // solution array List<Interval> sol = new List<Interval>(); // Traverse through given price array int i = 0; while (i < n - 1) { // Find Local Minima. Note that // the limit is (n-2) as we are // comparing present element // to the next element. while ((i < n - 1) && (price[i + 1] <= price[i])) i++; // If we reached the end, break // as no further solution possible if (i == n - 1) break ; Interval e = new Interval(); e.buy = i++; // Store the index of minima // Find Local Maxima. Note that // the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i - 1])) i++; // Store the index of maxima e.sell = i - 1; sol.Add(e); // Increment number of buy/sell count++; } // print solution if (count == 0) Console.WriteLine( "There is no day when buying the stock " + "will make profit" ); else for ( int j = 0; j < count; j++) Console.WriteLine( "Buy on day: " + sol[j].buy + " " + "Sell on day : " + sol[j].sell); return ; } // Driver code public static void Main(String []args) { StockBuySell stock = new StockBuySell(); // stock prices on consecutive days int []price = { 100, 180, 260, 310, 40, 535, 695 }; int n = price.Length; // function call stock.stockBuySell(price, n); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program for the above approach // This function finds the buy sell // schedule for maximum profit function stockBuySell(price, n) { // Prices must be given for at least two days if (n == 1) return ; // Traverse through given price array let i = 0; while (i < n - 1) { // Find Local Minima // Note that the limit is (n-2) as we are // comparing present element to the next element while ((i < n - 1) && (price[i + 1] <= price[i])) i++; // If we reached the end, break // as no further solution possible if (i == n - 1) break ; // Store the index of minima let buy = i++; // Find Local Maxima // Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i - 1])) i++; // Store the index of maxima let sell = i - 1; document.write(`Buy on day: ${buy} Sell on day: ${sell}<br>`); } } // Driver code // Stock prices on consecutive days let price = [100, 180, 260, 310, 40, 535, 695]; let n = price.length; // Function call stockBuySell(price, n); // This code is contributed by Potta Lokesh </script> |
输出
Buy on day: 0 Sell on day: 3Buy on day: 4 Sell on day: 6
时间复杂性： 外循环一直运行到我变成n-1。内部两个循环在每次迭代中增加I的值。所以总的时间复杂度是O（n）
谷峰进近：
在这种方法中，我们只需要找到下一个更大的元素，并从当前元素中减去它，使差值不断增加，直到达到最小值。如果序列是递减序列，那么可能的最大利润为0。
C++
#include <iostream> using namespace std; // Preprocessing helps the code run faster #define fl(i, a, b) for (int i = a; i < b; i++) // Function that return int maxProfit( int * prices, int size) { // maxProfit adds up the difference between // adjacent elements if they are in increasing order int maxProfit = 0; // The loop starts from 1 // as its comparing with the previous fl(i, 1, size) if (prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1]; return maxProfit; } // Driver Function int main() { int prices[] = { 100, 180, 260, 310, 40, 535, 695 }; int N = sizeof (prices) / sizeof (prices[0]); cout << maxProfit(prices, N) << endl; return 0; } // This code is contributed by Kingshuk Deb |
JAVA
// Java program for the above approach import java.io.*; class GFG { static int maxProfit( int prices[], int size) { // maxProfit adds up the difference between // adjacent elements if they are in increasing order int maxProfit = 0 ; // The loop starts from 1 // as its comparing with the previous for ( int i = 1 ; i < size; i++) if (prices[i] > prices[i - 1 ]) maxProfit += prices[i] - prices[i - 1 ]; return maxProfit; } // Driver code public static void main(String[] args) { // stock prices on consecutive days int price[] = { 100 , 180 , 260 , 310 , 40 , 535 , 695 }; int n = price.length; // function call System.out.println(maxProfit(price, n)); } } // This code is contributed by rajsanghavi9. |
Python3
# Python3 program for the above approach def max_profit(prices: list , days: int ) - > int : profit = 0 for i in range ( 1 , days): # checks if elements are adjacent and in increasing order if prices[i] > prices[i - 1 ]: # difference added to 'profit' profit + = prices[i] - prices[i - 1 ] return profit # Driver Code if __name__ = = '__main__' : # stock prices on consecutive days prices = [ 100 , 180 , 260 , 310 , 40 , 535 , 695 ] # function call profit = max_profit(prices, len (prices)) print (profit) # This code is contributed by vishvofficial. |
C#
// C# program for the above approach using System; class GFG{ static int maxProfit( int [] prices, int size) { // maxProfit adds up the difference // between adjacent elements if they // are in increasing order int maxProfit = 0; // The loop starts from 1 as its // comparing with the previous for ( int i = 1; i < size; i++) if (prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1]; return maxProfit; } // Driver code public static void Main( string [] args) { // Stock prices on consecutive days int [] price = { 100, 180, 260, 310, 40, 535, 695 }; int n = price.Length; // Function call Console.WriteLine(maxProfit(price, n)); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach function maxProfit(prices , size) { // maxProfit adds up the difference between // adjacent elements if they are in increasing order var maxProfit = 0; // The loop starts from 1 // as its comparing with the previous for (i = 1; i < size; i++) if (prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1]; return maxProfit; } // Driver code // stock prices on consecutive days var price = [ 100, 180, 260, 310, 40, 535, 695 ]; var n = price.length; // function call document.write(maxProfit(price, n)); // This code is contributed by umadevi9616 </script> |
输出
865
时间复杂性 ：O（n） 辅助的 空间： O（1）
本文由 阿什阿南德 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
