笔试强训 Day 20：经此一役小红所向无敌、连续子数组最大和、非对称之美
Day 20
经此一役小红所向无敌
解题思路：
- 数学模拟
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);longa=in.nextLong(),h=in.nextLong();longb=in.nextLong(),k=in.nextLong();longcnt=0;while(h>0&&k>0){cnt+=a+b;h-=b;k-=a;}if(k>0)cnt+=b*10;elseif(h>0)cnt+=a*10;System.out.println(cnt);}}连续子数组最大和
解题思路：
- 动态规划，dp[i] 表示以 i 为子数组末尾的最大和，看 dp[i-1] 是否大于0，大于 0 则加到连续数组中；
- 从所有局部最大值中，找到全局最大值；
代码实现：
importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadin=newRead();privatestaticPrintWriterout=newPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intn=in.nextInt();long[]nums=newlong[n];for(inti=0;i<n;i++)nums[i]=in.nextLong();longret=Integer.MIN_VALUE;long[]dp=newlong[n+1];for(inti=1;i<=n;i++){dp[i]=Math.max(dp[i-1]+nums[i-1],nums[i-1]);ret=Math.max(dp[i],ret);}out.println(ret);out.close();}}classRead{StringTokenizerst=newStringTokenizer("");BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringline=bf.readLine();if(line==null)returnnull;st=newStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}}非对称之美
解题思路：
- 如果整个字符串不是回文串，答案就是
n - 如果整个字符串是回文串：
- 如果所有字符都相同，那么任意子串都是回文串，答案是
0 - 否则答案是
n - 1
- 如果所有字符都相同，那么任意子串都是回文串，答案是
- 注意，需要单独判断所有字符是否都相同
原因：
- 如果原串不是回文，最长非回文子串就是它自己。
- 如果原串是回文但不全相同，删掉首字符或尾字符后，长度为
n - 1的子串一定至少有一个不是回文。
代码实现：
importjava.util.*;importjava.io.*;publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));char[]str=bf.readLine().toCharArray();// 判断字符串是否回文booleancheck=false;intn=str.length;for(intl=0,r=n-1;l<=r;){if(str[l]!=str[r]){break;}else{if(l==r||l+1==r)check=true;}l++;r--;}// 单独判断所有字符是否相等booleanallSame=true;for(inti=0;i<n;i++){if(i>0&&str[i]!=str[i-1]){allSame=false;}}// 整个字符串不是回文串, 最长 nintret=n;// 字符串所有字符都相同, 返回 0if(allSame)ret=0;// 字符串有字符不同, 但是整个字符串是回文串, 最长 n-1elseif(!allSame&&check)ret=n-1;System.out.println(ret);}}