7개의 댓글이 있습니다.

• 
  Being

  1차원 문제에 대해 해결하는 방법은 알고 계신가요?

  
  10년 전 link

• 
  Sharifa

  O(N^3)은 어렵지 않겠네요.
  

  임의의 두 행을 잡는다.(N^2)
  수열에서 연속한 부분 수열 값의 최댓값을 찾는 O(N) dp방법으로 푼다. (N) 이때 sum 배열을 미리 계산해 놓아 열의 부분 합을 O(1)만에 구할 수 있도록 한다.
  그래서 O(N^3)

  
  10년 전 link

• 
  amievil2

  1차원의 경우 답인지는 모르겠지만 생각해 보면 최대합의 후보집합을 Data[]라고 하면 오른쪽의 데이터를 추가하는 것과 기존의 Data[]에 왼쪽의 데이터를 버리는 것 중 어느것이 이익인지 계산해서 진행 해나가는... 뭐 이런식이 아닐까 생각만 하는데 자세한 건 어떻게 해야할 지 모르겠네요. 예를들어 추가와 버리는게 동일한 값을 같는 다던가 추가해도 버려도 손해가 난다 던가 하는 상황이요.

  
  10년 전 link

• 
  Being

  1차원 문제를 O(N)$O(N)$에 해결하는 방법을 찾으시면 위에서 Sharifa님이 말씀하셨듯 2차원 문제는 O(N^3)$O(N^3)$에 해결하실 수 있으실 거예요. 힌트를 드리자면,

  1. 답은 배열의 모든 부분구간, 즉 \frac{N(N-1)}{2}$\frac{N(N-1)}{2}$ 개의 구간 중 하나입니다.
  2. 이러한 구간들을, 마지막 원소의 위치별로 묶을 수 있습니다. 예를 들어 5번 원소가 마지막인 구간은 [1, 5], [2, 5], \cdots, [5, 5]$[1, 5], [2, 5], \cdots, [5, 5]$ 까지 있을 수 있겠지요.
  3. k$k$번 원소가 마지막인 여러 구간들 중 가장 큰 합을 내는 구간이 무엇인지 알고 있다고 가정해 보죠. 이 정보를 바탕으로 k+1$k+1$번 원소가 마지막인 경우에 대한 가장 큰 합을 내는 구간을 알아낼 수 있을까요?

  
  10년 전 link

• 
  amievil2

  흠... 원소의 집합을 N = {n_1, n_2 ..... n_N} 라고 하고 마지막 원소가 n_k이고 합이 최대값을 갖는 구간을 [n_a, n_k]라고 하면 k+1 번째 최대합 구간은 1. [n_a, n_k]의 합이 > 0 이면 [n_a, n_k+1] 2. [n_a, n_k]의 합이 <= 0 이면 [n_k+1, n_k+1] 이 되는 건가요? 이렇게 k=1 ~ k=N 까지 진행하면서 매번 합의 크기를 비교해 최대값을 저장해 놓으면 될까요? 이렇게 하면 2차원일 때는 이런 반복을 N(N-1)/2 만큼 반복해 주면 될것 같은데..... 제 생각이 맞나요?

  
  10년 전 link

• 
  Being

  맞습니다. :)

  
  10년 전 link

• 
  amievil2

  네. 도움 주셔서 정말 감사합니다. ^^

  
  10년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.