[LeetCode] 3652. Best Time to Buy and Sell Stock using Strategy

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-using-strategy/?envType=daily-question&envId=2025-12-18

LeetCode - Best Time to Buy and Sell Stock using Strategy

문제 유형: 구간 합, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given two integer arrays prices and strategy, where:

• prices[i] is the price of a given stock on the ith day.
• strategy[i] represents a trading action on the ith day, where:
  • -1 indicates buying one unit of the stock.
  • 0 indicates holding the stock.
  • 1 indicates selling one unit of the stock.

You are also given an even integer k, and may perform at most one modification to strategy. A modification consists of:

• Selecting exactly k consecutive elements in strategy.
• Set the first k / 2 elements to 0 (hold).
• Set the last k / 2 elements to 1 (sell).

The profit is defined as the sum of strategy[i] * prices[i] across all days.

Return the maximum possible profit you can achieve.

Note: There are no constraints on budget or stock ownership, so all buy and sell operations are feasible regardless of past actions.

 

prices와 straetgy배열을 받는다. prices에는 주식의 가격이, strategy에는 그 주식에 대한 전략이 들어있다. -1이면 1개 구매, 1이면 1개 판매, 0이면 홀드이다.

 

정수 k도 받는다. 당신은 이 연산을 최대 1번 할 수 있다.

 

k개의 연속된 strategy 배열에서 앞의 k/2부분의 전략을 0, 뒤의 k/2부분의 전략을 1로 모두 세팅한다.

 

이익은 모든 각각의 strategy[i] * prices[i]의 값의 합이다.

최대 가능한 값을 구하시오.

 

풀이

prefix sum을 구해두면, 편하게 값을 구할 수 있다.

그리고, 슬라이딩 윈도우를 통해서 연산의 범위에 대해 값을 구할 수 있다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loos");
static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
using ll = long long;
class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size(); 
        int k2 = k/2;
        vector<ll> pref(n+1, 0);

        for(int i = 0; i < n; i++) {
            pref[i+1] = pref[i] + 1LL * strategy[i] * prices[i];
        } 

		// 첫 k/2 ~ k윈도우의 합. (모두 1로 세팅된 것으로 가정한 부분)
        ll modify = reduce(prices.begin()+k2, prices.begin()+k, 0LL);
        // 첫 ans 초기화 = max(연산적용 안했을 시, 맨 앞 윈도우에 연산적용 시(그래서 윈도우값 + 전체 - 첫 k번범위 뺌)
        ll ans = max(pref[n], modify+pref[n]-pref[k]);

		// 이후, 윈도우를 밀면서 진행...
        for(int i = 1; i+k <= n; i++) {
            modify += prices[i+k-1]-prices[i+k2-1];
            ans = max(ans, modify+pref[n]-pref[i+k]+pref[i]);
        }

        return ans;
    }
};

 

Go

func maxProfit(prices []int, strategy []int, k int) int64 {
    n := len(prices) 
    k2 := k/2

    pref := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pref[i+1] = pref[i] + (int64(prices[i]) * int64(strategy[i]))
    }

    modify := int64(0)
    for i := k2; i < k; i++ {
        modify += int64(prices[i])
    }
    ans := max(pref[n], modify + pref[n] - pref[k])

    for i := 1; i + k <= n; i++ {
        modify += int64(prices[i+k-1] - prices[i+k2-1])
        ans = max(ans, modify + pref[n] - pref[i+k] + pref[i])
    }

    return ans
}

 

Rust

impl Solution {
    pub fn max_profit(prices: Vec<i32>, strategy: Vec<i32>, k: i32) -> i64 {
        let n = prices.len();
        let k = k as usize;
        let k2 = k/2;
        let mut pref = vec![0i64; n+1];
        for i in 0..n {
            pref[i+1] = pref[i] + (prices[i] as i64) * (strategy[i] as i64);
        }

        let mut modify = 0i64;
        for i in k2..k {
            modify += prices[i] as i64;
        }
        let mut ans = pref[n].max(modify + pref[n] - pref[k]);

        for i in 1..n-k+1 {
            modify += (prices[i+k-1] - prices[i+k2-1]) as i64;
            ans = ans.max(modify + pref[n] - pref[i+k] + pref[i]);
        }

        ans
    }
}