HDU1087

[java] 
package DP; 
 
import java.util.*; 
 
//狀態轉移方程 b[i]=max(b[i], b[j]+a[i]); 
public class HDU1087 { 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int n; 
        int[] a; 
        int[] b; 
        while (sc.hasNext()) { 
            n = sc.nextInt(); 
            if (n == 0) 
                break; 
            a = new int[n]; 
            b = new int[n]; 
 
            int sum = 0; 
 
            for (int i = 0; i < n; i++) { 
                a[i] = sc.nextInt(); 
            } 
            b[0] = a[0]; 
            for (int i = 1; i < n; i++) { 
                b[i] = a[i]; 
                for (int j = 0; j < i; j++) { 
                    if (a[i] > a[j] && b[i] < b[j] + a[i]) 
                        b[i] = b[j] + a[i]; 
                    if (sum < b[i]) 
                        sum = b[i]; 
                } 
            } 
            System.out.println(sum); 
 
        } 
 
    } 
 
}