アルゴリズムの検討——更に経典のアルゴリズムの問題を議論します:最も大きいサブシーケンスと、絶対値の最も大きいサブシーケンスとおよびその区間を求めます

アルゴリズムの検討——更に経典のアルゴリズムの問題を議論します:最も大きいサブシーケンスと、絶対値の最も大きいサブシーケンスとおよびその区間を求めます
任意の数値シーケンス、例えば{-5,4,-20,16,-2,-3}を与えて、その最も大きいサブシーケンスと、絶対値が最も大きいサブシーケンスと、対応する区間を求める.この例では、人肉計算で最も大きいサブシーケンスとは16であり、区間は[3,3)(配列の下に0から始まる)であり、絶対値が最も大きいサブシーケンスとは-21であり、区間は[0,2]であることが分かるが、アルゴリズムはどのように記述され、実現されるのだろうか.
古典的な書籍『データ構造とアルゴリズム分析C言語記述第2版』では、著者らは、時間的複雑度がO(N 3)からO(N)に低下し、最も大きなサブシーケンスと絶対値とその区間が私のこの問題に対する拡張であることを紹介した.
一、最大のサブシーケンスとその区間を求める
最大のサブシーケンス和を求めるアルゴリズムは比較的簡単で,動的計画思想を用いてO(N)に最適化することができ,問題の鍵は,前に入力した要素の計算結果が後の入力に依存しないことである.
O(N 2)アルゴリズム:N回の配列を巡回し、その中の各要素に対して、後続の各要素を巡回し続け、現在と比較して大きいことが判明した場合、現在と置換する.
C/C++実装:

 1 int maxsub(const int a[],int n)
 2 {
 3     int sum, max, i, j, begin, end;
 4     begin = end = max = 0;
 5     for(i = 0;i < n;i++)
 6     {
 7         sum = 0;
 8         for(j = i;j<n;j++)
 9         {
10             sum += a[j];
11             printf("the second level loop %d loop sum = %d
",j,sum);
12             printf("the second level loop %d loop max = %d
",j,max);
13             if(sum > max)
14             {
15                 max = sum;
16                 begin = i;
17                 end = j;
18             }
19         }
20         printf("the %d loop max = %d
",i+1,max);
21     }
22     printf("--final-- Begin = %d, End = %d
",begin,end);
23     return max;
24 }

サイクル終了後,beginとendの値,すなわち対応する区間.O(N)アルゴリズム:動的計画思想、on-line algorithmとも呼ばれる.すなわち、各入力に対して、後入力に依存せず、各入力に対して、直ちにその結果を計算し、保存し、その後の入力と比較し、和が大きくなると更新が発生する.和が常に小さくなると、前の入力を破棄します.
C/C++実装:

int maxsublinear(const int a[], int n)
{
    int i;
    int curSum = 0; /*       */
    int maxSum = 0; /*       */
    int begin = end = 0;

    /*           */
    for (i = 0; i < n; i++)
    {
        curSum = curSum + a[i];

        /*          ，         */
        if (curSum > maxSum)
        {
            maxSum = curSum;
            end = i;
        }

        /*       ，            */
        if (curSum < 0)
        {
            curSum = 0;
            begin = i + 1 >= n ? i : i + 1;
        }
    }
    return maxSum;
}

二、絶対値の最大のサブシーケンスと対応する区間を求める
この問題は第一の問題に対する拡張であるが,第一の問題よりも複雑であり,O(N 2)アルゴリズムは基本的に同じであり,容易に理解できる.
O(N 2)C/C++実現:

 1 int maxabssub(const int a[],int n)
 2 {
 3     int sum, max, i, j, begin, end;
 4     begin = end = max = 0;
 5     for(i = 0;i < n;i++)
 6     {
 7         sum = 0;
 8         for(j = i;j<n;j++)
 9         {
10             sum += a[j];
11             printf("the second level loop %d loop sum = %d
",j,sum);
12             printf("the second level loop %d loop max = %d
",j,max);
13             if(abs(sum) > max)
14             {
15                 max = abs(sum);
16                 begin = i;
17                 end = j;
18             }
19         }
20         printf("the %d loop max = %d
",i+1,max);
21     }
22     printf("--final-- Begin = %d, End = %d
",begin,end);
23     return max;
24 }

O(N)アルゴリズムは,竹の風がハスの池をなでるの学生の助けを得て,順調に解いた.考え方は実はとても简単で、绝対値の最大のサブシーケンスと、あるいは最大で、あるいは最小で、类似の问题の1中のO(N)アルゴリズム、同时にすべての入力が得ることができる最大とあるいは最小とを求めて、更に比较します.以下はC/C++コード実装です.
 

 1 int maxAbsSubLinear(int a[], int n)
 2 {
 3     int posiSum, negaSum, curSum, max, j, begin, end, posiBegin, posiEnd, negaBegin, negaEnd, flag;
 4     posiSum = negaSum = curSum = max = j = begin = end = posiBegin = posiEnd = negaBegin = negaEnd = flag = 0;
 5 
 6     for(j = 0;j < n;j++)
 7     {
 8         if(posiSum + a[j] > a[j])
 9         {
10             posiSum += a[j];
11         }
12         else
13         {
14             posiSum = a[j];
15             posiBegin = j;
16         }
17         if(negaSum + a[j] < a[j])
18         {
19             negaSum += a[j];
20         }
21         else
22         {
23             negaSum = a[j];
24             negaBegin = j;
25         }
26 
27         if( abs(posiSum) > abs(negaSum) )
28         {
29             curSum = abs(posiSum);
30             posiEnd = j;
31             flag = 1;
32         }
33         else
34         {
35             curSum =  abs(negaSum);
36             negaEnd = j;
37             flag = 0;
38         }
39 
40         if(curSum > max)
41         {
42             max = curSum;
43             if(flag)
44             {
45                 begin = posiBegin;
46                 end = posiEnd;
47             }
48             else
49             {
50                 begin = negaBegin;
51                 end = negaEnd;
52             }
53         }
54 
55         printf("IN ABS LINEAR -- LOOP %d, posiSum = %d, negaSum = %d, curSum = %d, max=%d, begin = %d, end = %d
", j+1, posiSum, negaSum, curSum, max, begin, end);
56     }
57 
58     printf("--LINEAR final-- Begin = %d, End = %d
",begin,end);
59     return max;
60 }

 
竹の風がハスの池をなでるさんに改めて感謝します.