maxsubarray （配列の中の要素を一つずつ調べて、足していって一番大きくなるもの)

Question

こんにちは
今、Maximum Sum arrayの問題を解いているのですが、
関数の返し方と、自分が指定した数に一番近いMaximum Sumを実装しようとしているところで詰まってします。
関数を返そうしたところで出力に問題が出てしまうのですが、自分じゃ見つけられなくて質問させていただきました。
指摘していただけたらと思います。

#include <stdio.h>

int sum_Function(int* nums, int i, int j){

int sum=0;

for(i;i<j; i++){
    
    sum+=nums[i];
    
}

return sum;
}

int maxSubArray(int* nums, int numsSize){

int max=0;
int i=0;
int j=numsSize;
int temp=0;

for(i=0; i<numsSize; i++){
    
    for(j=numsSize; j>i; j--){
        
        temp = sum_Function(nums,i,j);
        
        if(max<temp){
            
            max=temp;
        }
        
    }
       
}
return max;
}

int main(){

    int n;
    scanf("%d",&n);
　int nums[n];
    for(int i=0;i<n;++i){
        scanf("%d",&nums[i]);
    }
    
     n = sizeof(nums) / sizeof(int);
    
    int max = maxSubArray(nums,n);
    printf("%d",max);
    return 0;
}
コード

Ex:入力したい値
10 55 //10個の数を入力して(最大要素数は20個)、55に一番近い合計を返す。（55は超えたらいけない
2 9 6 7 8 3 4 5 10 2//大きさ10の配列の要素で全て正の数、負の数はなし
出力したい値
54
まだ、自分で合計の数字に一番近くする入力するコードを実装していないものです。

私が書いたコードは、配列の大きさを入力した後、その大きさ分の要素を入力したものです。
配列の大きさ分の要素を入力するところまではあっているはずです。
ただ、求めたい配列の要素の合計に一番近い値を出入力するところが思いつきません

Comments

[y_waiwai]

提示のコードはどういう動作をしていて、どういう問題があるんでしょうか。
そして、どういう出力にしたいという話でしょうか

[dodox86]

> 今、Maximum Sum arrayの問題を解いているのですが、

唐突に「Maximum Sum arrayの問題」と書かれても、読んだ者には？？？だと思いますよ。
どこかの競技プログラミング系の問題だと思いますが、そのリンクを示しましょう。

また、当該問題の解法自体が思いつかないのか、解法は思いついているけどコードが正しいかどうか分からないのか、それも読んだ者に分からないので、もう少しちゃんと説明しましょう。

[BeatStar]

問題文があるページを張った方がいいですよ。質問者さんにとっては当たり前でも他のユーザからは当たり前ではありません。最悪でも「AtCoder」なのかなんなのかぐらいは書きましょう。

それと、プログラミングするなら『デバッグ』ぐらいはしましょう。プログラミングは「書いて終わり」…ではありません。デバッグと呼ばれる、エラーに対処することも含まれます。当たり前の技術です。

[BeatStar]

繰り返します!!! 問題文があるページを張った方がいいですよ。質問者さんにとっては当たり前でも他のユーザからは当たり前ではありません。最悪でも「AtCoder」なのかなんなのかぐらいは書きましょう。

それと、プログラミングするなら『デバッグ』ぐらいはしましょう。プログラミングは「書いて終わり」…ではありません。デバッグと呼ばれる、エラーに対処することも含まれます。当たり前の技術です。

[BeatStar]

それと、タグが滅茶苦茶。「標準入力」とかはまだわからんでもないけど、「関数型プログラミング」は明らかに関係ない。
質問者さんは『パン』とついているのだから、フライパンも同じだろ。と考えるお人なのでしょうか。それなら構いません。(いや、良くないけど)

関数型プログラミングは関数とはまったく関係がありません。(少しは被るが殆ど関係ない)
実際にWikipediaなりで調べてみてください。

[episteme]

一番近いって...超えてもいいの?

[kazuma-s]

> 配列の大きさ分の要素を入力するところまではあっているはずです。
nums[0] に 55 が入るので合っていません。

> n = sizeof(nums) / sizeof(int);
10 だった n の値が 100 になってしまいます。

[kazuma-s]

質問の入力例は 10個の数がすべて正ですが、負の数が入る場合もあるのでしょうか？

[dodox86]

本欄の皆さんの指摘が伝わっていないのだと思いますが、例えば10個の数値が入力として与えられた時、先頭から順番に、とは限らないのですよ。最適な任意の個数の数値の組み合わせかもしれない。個数の上限があるかもしれない。それは問題を読まないと判断できません。そういったことは考えなくて良い質問なのでしょうか。

[dodox86]

「個数の上限」とは問題で与えられる入力データの個数の最大数を言っています。組み合わせを考える場合、現実的な時間でプログラムが終わる値が指定されたりします。100個の数値が与えられる様な時、、とんでもない時間がかかる場合があります。

[jimbe]

ナップザックのように見えますが・・・まぁ、
https://en.wikipedia.org/wiki/Maximum_subarray_problem
でしょうね。これに上限を追加すると。

ただ
> 関数を返そうしたところで出力に問題が出てしまう
が何を言っているのかが分かりません。
関数を返している所は無さそうですし、出力に問題とは?

> ～あっているはずです
「はず」という希望では無く、maxSubArray を呼ぶ直前で nums や n が想定通りの値となっているかを確認してください。

そもそもご提示のコードで上限値を取り込もうとした形跡もありませんし、余計なコードで動作不良を起こしているようですので、まずはそれらをしっかり直されるのが良いかと思います。

Answer 1

超えてはいけない制限値を追加するだけですよね。

-int maxSubArray(int* nums, int numsSize){
+int maxSubArray(int* nums, int numsSize, int limit){
 
-        if(max<temp){
+        if(temp <= limit && max<temp){
 
-    int n;
-    scanf("%d",&n);
-　int nums[n];
+    int n, limit;
+    scanf("%d%d",&n,&limit);
+    int nums[n]; // ★ int の前の全角スペースを半角に
 
-     n = sizeof(nums) / sizeof(int);
+     //n = sizeof(nums) / sizeof(int);
 
-    int max = maxSubArray(nums,n);
-    printf("%d",max);
+    int max = maxSubArray(nums,n,limit);
+    printf("%d\n",max);

-コード
+//コード

上の修正で動くはずですが、2重の forループの中で maxSubArray を呼出し
その中でまた forループがあるという 3重ループで非効率です。
i以上 j未満の和が分かっていたら、i以上 (j+1)未満の和は、再計算せず、
i以上 j未満の和に nums[j] を足すだけで求まります。
負の数がないのなら、制限値を超えた場合の判定がもっと早くできます。