最大子段和

分析

• 暴力算法復(fù)雜度是O(N^3)
• 可以對暴力算法進(jìn)行優(yōu)化，將時間復(fù)雜度降為O(N^2)
• 利用分治算法

代碼

暴力算法

前兩重循環(huán)用i，j分別定義子段的起點(diǎn)與終點(diǎn)，第三重循環(huán)計(jì)算子段和。

import java.io.*;
import java.util.*;

public class function {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        int a[] = new int[50010];
        n = in.nextInt();
        for(int i=0;i<n;i++) {
            a[i] = in.nextInt(); // 還需要驗(yàn)證是否都是負(fù)數(shù)
        }
        int res0 = merge(a, 0, n-1);
        int res = enumeration(a,n);
        int res1 = opti_enumeration(a,n);
        System.out.println(res0);
        System.out.println(res);
        System.out.println(res1);
//      out.println(res);
        out.flush();
    }
    public static int enumeration(int[] a,int n) {
        int sum=0;
        int max = 0;
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                for(int k=i;k<=j;k++) {
                    sum+=a[k];
                    if(max < sum)
                        max = sum;
                }
                sum =0;
            }
        }
        return max;
    }

優(yōu)化暴力算法

第三重循環(huán)可以省略，因?yàn)樗M(jìn)行了大量的重復(fù)計(jì)算。根據(jù)公式

我們可以對算法進(jìn)行改進(jìn)。

public static int opti_enumeration(int[] a,int n) {
        int sum=0;
        int max = 0;
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                sum+=a[j];
                if(max < sum)
                    max = sum;
            }
            sum=0;
        }
        return max;
    }

分治算法

分治思想：
將整個序列等分為兩部分a[1,n/2]與a[n/2+1,n]，則最大子段有三種情形：

1. 出現(xiàn)在左半部分
2. 出現(xiàn)在右半部分

3. 跨越左半部分與右半部分，其中一定包括a[n/2]與a[n/2+1]。
   對于情形3，我們可以在a[1,n/2]中計(jì)算出s1，在a[n/2+1,n]中計(jì)算出s2。s1+s2就是情形3的最大子段和。

   
   
   

public static int merge(int[] a, int low, int high) {
        if(low >= high)
            return 0 ;
        int mid = (low+high) / 2;
        int left = merge(a, low, mid);  //前半段的最大字段和
        int right = merge(a, mid+1, high);//后半段的最大字段和
        int i=mid;
        int j=mid+1;
        int left_max = 0;
        int right_max = 0;
        int sum=0;
        while(i>=low) {
            sum+=a[i--];
            if(left_max < sum)
                left_max = sum;
        }
        sum = 0;
        while(j<=high) {
            sum += a[j++];
            if(right_max < sum)
                right_max = sum;
        }
        return Math.max(left_max + right_max, Math.max(left, right)); 
    }

參考

[1]動態(tài)規(guī)劃】最大子段和問題，最大子矩陣和問題，最大m子段和問題