読者です 読者をやめる 読者になる 読者になる

Max Range Sum(CODEEVAL)

配列から連続したN個を取り出し、合計数の最大値を算出する問題。
最初のinjectの引数を無しで書いてしまったため、10分ほど悩んでしまいました。
injectあるあるについて補足。

CHALLENGE DESCRIPTION:

Bob is developing a new strategy to get rich in the stock market. He wishes to invest his portfolio for 1 or more days, then sell it at the right time to maximize his earnings. Bob has painstakingly tracked how much his portfolio would have gained or lost for each of the last N days. Now he has hired you to figure out what would have been the largest total gain his portfolio could have achieved.
 
For example:
 
Bob kept track of the last 10 days in the stock market. On each day, the gains/losses are as follows:

7 -3 -10 4 2 8 -2 4 -5 -2

If Bob entered the stock market on day 4 and exited on day 8 (5 days in total), his gains would have been

16 (4 + 2 + 8 + -2 + 4)

INPUT SAMPLE:

The input contains N, the number of days (0 < N < 10000), followed by N (separated by symbol “;”) integers D (-10000 < D < 10000) indicating the gain or loss on that day.

5;7 -3 -10 4 2 8 -2 4 -5 -2
6;-4 3 -10 5 3 -7 -3 7 -6 3
3;-7 0 -45 34 -24 7

OUTPUT SAMPLE:

Print out the maximum possible gain over the period. If no gain is possible, print 0.

16
0
17

CONSTRAINTS:

  1. Gain or loss on that day is (-100 < D < 100).
  2. Number of days (0 < N < 100).
  3. Number of test cases is 20.

My Code

#!/usr/bin/env ruby -w

def max_profit(n, incomes)
  (0..(incomes.size - n)).inject(0) do |max_sum, i|
    [max_sum, incomes[i, n].inject(&:+)].max
  end
end

ARGF.each_line do |line|
  day, data = line.chomp.split(";")
  incomes = data.split.map(&:to_i)
  puts max_profit(day.to_i, incomes)
end

余談

injectの引数有無の結果。

n = 4
incomes = [1, 2, 3, 4]

# case1.引数あり(正しい結果が返る)
[0].inject(0) do |max_sum, i|
  [max_sum, incomes[i, n].inject(&:+)].max
end
=> 10

# case2.引数無し
[0].inject do |max_sum, i|
  [max_sum, incomes[i, n].inject(&:+)].max
end
=> 0

# case3.引数無しでも対象のObjectの数が2つ以上ある場合(正しい結果が返る)
[0, 1].inject do |max_sum, i|
  [max_sum, incomes[i, n].inject(&:+)].max
end
=> 9

 

case1, 2の違いは

injectのblockパラメータである max_sum, i に渡される最初の値が異なります。
case1 だとmax_sumには第一引数の値0、iには配列の最初の値0 が渡りblockが実行されますが
case2 だとmax_sumに配列の最初の値0がセットされ、iには値がセットされずにblockが実行されずに終わってしまいます。
case3だとmax_sumに配列の最初の値0がセットされ、iには配列の次の値1がセットされblockが実行されます。

なので

inject利用時には、適切に第一引数の設定を行う必要があります。