P1115 最大子段和 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
題目要求求連續(xù)得一段子串使其累加和最大。
我們做動(dòng)態(tài)規(guī)劃首先考慮小情況，然后推而廣之。
假設(shè)三個(gè)數(shù)1，-2，5.
我們先選1然后我們?cè)?2以及-2加1里邊選，我們選-1，接著我們?cè)?1以及5里邊選我們選擇5
由此我們發(fā)現(xiàn)我們選擇是從以第n-1個(gè)數(shù)結(jié)尾的最長(zhǎng)長(zhǎng)度加上第n個(gè)數(shù)同第n個(gè)數(shù)比取最大的。
正如我們?cè)谂袛嗟诙€(gè)數(shù)-2時(shí)，我們不確定加上第二個(gè)數(shù)是否可行，因?yàn)橐筮B續(xù)，所以我們
針對(duì)第二個(gè)數(shù)的策略只有加與不加，不加就從第二個(gè)數(shù)開(kāi)始為起點(diǎn)加的話就累加，算最大的。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-662983.html
同時(shí)我們還要在以某個(gè)數(shù)為終點(diǎn)的累加中取最大的。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-662983.html
import java.awt.FontFormatException;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.net.DatagramPacket;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.plaf.ColorChooserUI;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
import javax.xml.crypto.dsig.spec.DigestMethodParameterSpec;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br1.readLine().split(" ");
int a=Integer.parseInt(aStrings[0]);
aa=new int[a];
String[] bStrings=br1.readLine().split(" ");
int b;
for(b=0;b<a;b++) {
aa[b]=Integer.parseInt(bStrings[b]);
}
int[] dp=new int[a+1];
dp[0]=aa[0];
int answer=aa[0];
for(b=1;b<a;b++) {
dp[b]=Math.max(aa[b], dp[b-1]+aa[b]);
answer=Math.max(answer, dp[b]);
}
System.out.println(answer);
}
public static int[] aa;
}
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃入門之線性動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
