[욕심 알고리즘] [동적 기획] 주식 매매 의 적기 II
1867 단어 알고리즘 문제
배열 을 지정 합 니 다. i 하나의 요 소 는 주어진 주식 제 이다. i 하늘의 가격.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 가능 한 한 더 많은 거래 를 완성 할 수 있다.
주의: 당신 은 여러 가지 거래 에 동시에 참여 할 수 없습니다.
예시 1:
: [7,1,5,3,6,4]
: 7
: 2 ( = 1) , 3 ( = 5) , = 5-1 = 4 。
, 4 ( = 3) , 5 ( = 6) , = 6-3 = 3 。
예시 2:
: [1,2,3,4,5]
: 4
: 1 ( = 1) , 5 ( = 5) , = 5-1 = 4 。
1 2 , 。
, 。
예시 3:
: [7,6,4,3,1]
: 0
: , , 0。
해법 1:
class Solution {
public int maxProfit(int[] prices) {
if(null == prices || prices.length == 0){
return 0;
}
int max = 0;
for(int i = 1; i < prices.length; i++){
max += Math.max(prices[i] - prices[i - 1], 0);
}
return max;
}
}
해법 2:
class Solution {
public static int maxProfit(int[] prices) {
if(null == prices || prices.length <= 1){
return 0;
}
int[][] dp = new int[prices.length][prices.length];
for(int i = 0; i < prices.length; i++){
for(int j = i; j < prices.length; j++){
int tmp = Math.max(j > 0 ? dp[i][j - 1] : 0, i > 0 ? dp[i - 1][j] : 0);
tmp = Math.max(tmp, prices[j] - prices[i] + (i > 0 ? dp[i - 1][i - 1] : 0));
dp[i][j] = tmp;
}
}
return dp[prices.length - 1][prices.length - 1];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[못 푼 문제] 백준 10989번sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.