121.Best Time to Buy and Sell Stock

Say you have an array for which theithelement isthe price of a given stock on dayi.

If you were only permitted to complete at most one transaction (ie, buyone and sell one share of the stock), design an algorithm to find the maximumprofit.

HideTags

ArrayDynamic Programming

#pragma once#include<iostream>#include<vector>using namespace std;/*i+1 减去i ，，构造每天盈利数组，求子数组最大和*///求子数组最大和，若和为负，应返回0int findMax(int *list, int n){int maxsum = 0;//初始设为0，可保证最后返回大于等于0int sum = 0;for (int i = 0; i < n;i++){sum += list[i];if (sum > maxsum)maxsum = sum;elseif (sum <= 0)sum = 0;}return maxsum;}int maxProfit(vector<int> &prices) {if (prices.size() == 0)return 0;int *list = new int[prices.size() – 1];for (int i = 0; i < prices.size() – 1; i++)list[i] = prices[i + 1] – prices[i];return findMax(list, prices.size() – 1);}void main(){system("pause");}

坐在外婆的沙滩，看最白的帆影。