部分列の最大合計 (4 通り)

1. 問題の説明

一連の整数を入力し、この一連の数値の部分列の合計の最大値を見つけます。つまり、最大のシーケンスではなく、最大のサブシーケンスの合計を見つけるだけで済みます。例:

1. Sequence: -2 11 -4 13 -5 -2 の場合、サブシーケンスの合計の最大値は 20 です。
2. シーケンス: -6 2 4 -7 5 3 2 -1 6 -9 10 -2 の場合、サブシーケンスの合計の最大値は 16 です。

2. PHP コードの実装

実装については、以下を参照してください。 http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html

テスト

<?php/** * 找出最大子序列和 */// 方法一、 最暴力的方法 O(N^3)function findMax1($data){    $max_value = 0;    $max_start = 0;    $max_end = 0;    $data_num = count($data);    for($i=0;$i<$data_num;$i++){        for($j=$i;$j<$data_num;$j++){            $sum = 0;            $temp = array();            for($k=$i;$k<=$j;$k++){                $temp[] = $data[$k];                $sum += $data[$k];            }            if($max_value < $sum){                $max_value = $sum;                $max_start = $i;                $max_end = $j;            }        }    }    return array($max_value,$max_start,$max_end);}//方法二、 记录上一次的结果  O(N^2)function findMax2($data){    $max_value = 0;    $max_start = 0;    $max_end = 0;    $data_num = count($data);    for($i=0;$i<$data_num;$i++){        $last_sum = 0;        for($j=$i;$j<$data_num;$j++){            $sum = $last_sum+$data[$j];            if($max_value < $sum){                $max_value = $sum;                $max_start = $i;                $max_end = $j;            }            $last_sum = $sum;        }    }    return array($max_value,$max_start,$max_end);}//方法三、分而自治算法 O(NlogN)function findMax3($data,$start=0,$end=0){    if($start >= $end){        $max_value =  isset($data[$start])?$data[$start]:0;    }else{        $mid = floor(($start+$end)/2);        list($max_left_value,$max_left_start,$max_left_end) = findMax3($data,$start,$mid);        list($max_right_value,$max_right_start,$max_right_end) = findMax3($data,$mid+1,$end);        //计算左边的最大值        $max_this_value = $data[$mid];        $max_this_start = $mid;        $max_this_end = $mid;        $temp = 0;        for($i=$max_this_start;$i>=$start;$i--){            $temp += $data[$i];            if($temp > $max_this_value){                $max_this_value = $temp;                $max_this_start = $i;            }        }        //计算右边的最大值        $temp = $max_this_value;        for($i=$max_this_end+1;$i<=$end;$i++){            $temp += $data[$i];            if($temp > $max_this_value){                $max_this_value = $temp;                $max_this_end = $i;            }        }        $max_value = $max_this_value;        $start = $max_this_start;        $end = $max_this_end;        if($max_value < $max_left_value){            $max_value = $max_left_value;            $start = $max_left_start;            $end = $max_left_end;        }        if($max_value < $max_right_value){            $max_value = $max_right_value;            $start = $max_right_start;            $end = $max_right_end;        }    }    return array($max_value,$start,$end);}//方法四、找规律算法  O(N)function findMax4($data){    $max_value = 0;    $thisSum = 0;    $data_len = count($data);    $start = 0;    $end = 0;    for($i=0;$i<$data_len;$i++){        $thisSum += $data[$i];        if($thisSum > $max_value){            $max_value = $thisSum;            $end =$i;        }else if($thisSum < 0){            $thisSum = 0;            $start= $i+1;        }    }    return array($max_value,$start,$end);}

4テスト結果

n=1000

1. テスト結果: n=1000

n=5000

まだテスト中、最初の解決策は遅すぎます