MaxProfit
[최초풀이]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
maxP = 0
for i in range(len(A)):
for j in range(i+1, len(A)):
if maxP < A[j]-A[i]:
maxP = A[j]-A[i]
return maxP
[다른 풀이]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if (len(A) == 1 ) or (len(A) == 0):
return 0
minP = A[0]
tempMaxP = 0
MaxP = 0
for i in range(len(A)):
tempMaxP = A[i] - minP
if A[i] < minP :
minP = A[i]
MaxP = max(tempMaxP, MaxP)
if MaxP < 0:
return 0
return MaxP
MaxSliceSum
[최초풀이]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if (len(A) == 1):
return A[0]
if max(A) <0:
return max(A)
tempMaxS = 0
MaxS = 0
for i in range(len(A)):
if A[i] >= 0:
tempMaxS += A[i]
else:
tempMaxS = 0
MaxS = max(tempMaxS, MaxS)
return MaxS
-> 원소가 음수가 나온다고 해서 무조건 리셋시키면 안된다,
-> 더한 결과가 음수가 나왔을 때만 리셋,
-> 원소가 음수가 나오더라도 더한 결과가 아직 양수이면 계속 이어나가서 더 큰 합을 만들 수 있기 때문
[다른풀이]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
tempS = 0
maxS = -10000000
for x in A:
maxS = max(maxS, tempS + x)
tempS = max(0, tempS + x)
return maxS
MaxDoubleSliceSum
[풀이]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
leftMaxS = [0]*len(A)
rightMaxS = [0]*len(A)
for i in range(1, len(A)-1):
leftMaxS[i] = max(0, leftMaxS[i-1] + A[i])
for i in range(len(A)-2, 0, -1):
rightMaxS[i] = max(0, rightMaxS[i+1] + A[i])
maxS = 0
for i in range(1, len(A)-1):
maxS = max(maxS, rightMaxS[i+1] + leftMaxS[i-1])
return maxS
