部分区間和の最大値を求めたいです。

Question

長文失礼いたします。

要件

整数値の列 d0, d1, ..., dn-1 （長さ n）に対して、その部分区間 dp, dp+1,..., dq-1 (0≦p≦q＜n）の和の最大値を求めたいです。

入力：
標準入力から列の長さ n (0＜n＜10000000）が与えられる。
対象とする数値列の数値は、関数呼出し dataset(n); を行った後、関数呼出し nextdata() を行うと整数値 d0, d1, ..., dn-1 が次々と順に得られる。

  ※この関数呼出し nextdata() を n 回を超えて呼び出そうとするとプログラムの実行が打ち切られます。

出力：
この整数値の列 d0, d1, ..., dn-1 の部分区間 dp, dp+1,..., dq-1 (0≦p≦q＜n）の和の最大値を書き出す。

※関数は別ファイルに定義してあります。

コード

#include <stdio.h>
#include <limits.h>

#define MAX_CNT 1000

    int getSum(int array[], int from, int to) {
    int sum = 0, i;
    for (i = from; i <= to; i++) {
    sum += array[i];
    }
    return sum;
    }

    void dataset(int n); 
    int nextdata(void);

int main(int argc, char *argv[]){
    
    int n, z;
    scanf("%d", &n);
    dataset(n);
    
    int answer = 0;
    
    int array[9999999] = {0};
    
    for(z=0; z<=n-1; z++) {
        array[z] = nextdata();
    }

    int sum = 0, max = INT_MIN, from, to, j, i;

    for (i = 0; i < MAX_CNT; i++) {
        for (j = i; j < MAX_CNT; j++) {
            sum = getSum(array, i, j);
                if (max < sum) {
                    max = sum;
                    from = i;
                    to = j;
                }
        }
    }


for (i = from; i < to; i++) {
    answer = answer + array[i];
}

answer = answer + array[to];

printf("%d\n", answer);

return 0;
}

うまくいかない点

標準入力値が10000を超えると標準出力の値が正しい答えと異なった値が出力されます。

int型ではなくほかの型を使用する必要があるのでしょうか？
それともほかの場所が間違っているのでしょうか？
わかる方がいらっしゃいましたら、ご教授お願いいたします。

Comments

[HogeAnimalLover]

dataset関数とnextdata関数の定義が見当たりません。宣言はありますけど。

[jimbe]

部分区間の p と q はどういう値なのでしょうか.
「和の最大値」とはいったいなんでしょう.

Answer 1

期待どおりの結果にならない原因

0<n<10000000

という条件にもかかわらず

#define MAX_CNT 1000

というなんだかよくわからない定数を用いてMAX_CNTの範囲の二重ループで最大値を求めようとしてますね。そこが根本的におかしい点だと思います。与えられたnだけが必要であり、MAX_CNTという定数を定義すること自体に意味が認められません。

いくつかの指摘

(1) 問題の内容にある部分数列の範囲は

dp, dp+1, ..., dq-1 (0≦p≦q＜n）

ではなく

dp, dp+1, ..., dq (0≦p≦q＜n）

だと思います。そうでないと入力データの最終要素dn-1はなんら結果に寄与しないので無意味となってしまいます。

(2) 質問者さんのプログラムの効率
質問者さんのアルゴリズムの計算量はO(N^3)だと思います。しかし問題の条件をよく考えればO(N)の計算量で結果が出ます。また配列arrayに入力データを全部覚える必要もありません。質問者さんのアルゴリズム(の方針)は正しい結果を出すこと自体はできるものの効率がよくないため例えばAtCoderのような「計算効率をも問う問題サイト」では正解とはみなされないと思います。
(追記: 上記の'^'はべき乗の意味です)

この問題は「最大部分配列 問題」という結構ポピュラーな問題で、効率のよい計算方法については「Kadane’s Algorithm」というキーワードで調べると出てくると思います。

(3) プログラムのスタイルなど
C言語のプログラムの書き方に気になる点がいくつかあります。アルゴリズムを考えるのも大事ですが「自分や他人が見てなるべくわかりやすいコードを書く」ことも大切ですので、その点も心がけましょう。

(A) 字下げ(インデンテーション)の仕方が変
(B) 変数スコープが無駄に長い

int sum = 0, i;
for (i = from; i <= to; i++) {
  sum += array[i];
}
return sum;

とすると変数iはfor文以降でもアクセスできるがその必要はない。ここは

int sum = 0;
for (int i = from; i <= to; i++) {
  sum += array[i];
}
return sum;

と書きたいところ。

(4) 追記：ローカル変数に巨大な配列を定義している
ローカル変数arrayですが、これほど巨大な大きさの配列をローカル変数として定義することは通常「よくない」と思います。どこまでならゆるされるかをはっきり言えないのですが自分ならせいぜい1000要素程度(数KB程度)が限度だと思っています。またローカル変数のバイト数がある程度以上大きな関数は再帰呼び出しを避けるといった注意も必要になるでしょう。大きな配列がどうしても必要ならグローバル変数とするか、mallocなどでヒープから動的に確保すべきだと思います。グローバル変数/mallocのどちらにすべきかはケースバイケースだと思います。