Let's challenge LeetCode!! _2
こんばんは(*´ω｀)
二回目は何故か日本語で行きます。
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
--ザックリ翻訳-----
与えられた株の売値、買値が i th day まで先読みできたとします。
買う前に売ることは勿論できませんが、1日に出来るのは売り or 買い の何れかです。
利益の最大値を求めてみましょう。
これは間違いなく、DP!! っと意気揚々と
以下のコードを書いてみたがあえなく撃沈。。。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [0 for m in range(len(prices))]
if len(prices) <= 0:
return 0
for i in range(1,len(prices),1):
for j in range(i):
if prices[i] - prices[j] > 0:
dp[i] = max(dp[i-1],dp[i],prices[i]-prices[j])
else:
dp[i] = dp[i-1]
return dp[-1]
時間が掛かりすぎるようです。
用意しているノートをコンパクトにし、
1 つのセルを死ぬほど更新してみようと思いました。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
Mval = 0
for i in range(len(prices)-1):
for j in range(i+1,len(prices),1):
Cval = prices[j]-prices[i]
if Cval > Mval:
Mval = Cval
return Mval
残念ながら、これも time over。。
やっぱり for のネストが良くないだと思います。
クリアするためには n に抑える必要がありそうです。
そこで以下のコードに辿り着きました。
class Solution:
if len(prices) == 0:
return 0
dp = [0 for i in range(len(prices))]
for i in range(1,len(prices)):
dp[i] = prices[i]-prices[i-1]
CM = [0 for i in range(len(prices))]
for j in range(1,len(prices)):
CM[j] = max(dp[j],CM[j-1]+dp[j])
return max(CM)
for 文をネストして切り抜けようとする考えを捨ててみました。
例えばですが、data[3] - data[2] に data[2] - data[1] を足すとどうなりますか？
data[3] - data[1] になりますよね？
前述だと data 長が [0] ~ [3] だった場合、
全てのケースを比較した選定は出来ませんが、
maxを使って、常に最大値を記録していたので全部やる必要が無いのです。
最後ですが、以下の記述を見つけて、自分は度肝を抜かれました。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_price = 0
price = 0
for i , high in enumerate(prices):
if i == 0 or high < low:
low = high
else:
max_price = high - low
if max_price > price:
price = max_price
return price
prices[0] を最小値と設定します。
これを基準に利益の最大値を更新していきます。
しかし、このコードの素晴らしい所は、最小値も
常に更新し、利益を記録している所です。
無理に表に落とすことなく、パラメータ用の箱をそれぞれ用意して、
その箱の中を都度更新していきます。
勿論、for 文のネスト無しで実現しています。
これが easy だって。
やばい。。(笑)
--12/13 upload------------------
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
--ザックリ翻訳-----
与えられた配列で隣接する要素の和の最大値を求めてください。
補足:もし計算量 O(n) が出来た場合は、割り算、conquer solution(!?) で考えてみてください。
もっとムズイけど。。
※conquer solution ってなんだべ！？(*´з`)
いつも通り解いてしまいました。
class Solution:
def maxSubArray(self, nums):
dp = [-10 for i in range(len(nums))]
#print(dp)
Vsum = 0
if len(nums) == 1:
return nums[0]
if len(nums) == 0:
return 0
for i in range(len(nums)):
for j in range(i,len(nums)):
for k in range(i,j+1):
Vsum = Vsum + nums[k]
#print(Vsum)
dp[i] = max(dp[i],Vsum)
#print(dp)
Vsum = 0
return max(dp)
どうしても for に頼ってしまう(´；ω；`)ｳｩｩ
しかも今回は 3 重でした。
勿論、time over です。
分からなかったので有識者のコードを
拝見しました。
class Solution:
def maxSubArray(self, nums):
n = len(nums)
max_sum = nums[0]
for i in range(1, n):
if nums[i - 1] > 0:
nums[i] += nums[i - 1]
max_sum = max(nums[i], max_sum)
return max_sum
読んでビックリしました。
nums[i] そのものを編集し、書き換えていきます。
どうしたら、そんな発想が湧くのでしょうか、、驚きです。
この nums[i] と max_sum を比較し、常に最大値を保ちます。
これも easy!?
もう倒れそうです。。
Author And Source
この問題について(Let's challenge LeetCode!! _2), 我々は、より多くの情報をここで見つけました https://qiita.com/AKpirion/items/26cd5b1773a471b9b238著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .