自动优化网站软件没有了,vs简易新闻建设网站,甜品网站模板代码,注册公司一般流程大家好#xff0c;我是晴天学长#xff0c; 一个找连续子数组最大和的变形题#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .环形数组的连续子数组的最大和 描述 给定一个长度为 nn 的环形整数数组我是晴天学长 一个找连续子数组最大和的变形题需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .环形数组的连续子数组的最大和 描述 给定一个长度为 nn 的环形整数数组请你求出该数组的 非空 连续子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。例如对于数组 [1,3,-5,2,-4][1,3,−5,2,−4]而言第一个数 11的前一个数是最后一个数 -4−4。 输入描述 第一行输入一个正整数 nn 代表数组的长度。 第二行为 nn 个整数 ai
输出描述 输出一个整数为原数组的非空子数组的最大可能和。 示例1 输入 3 5 -3 5 输出 10 说明 从子数组 [5,5] 得到最大和 5 5 10 示例2 输入 4 3 -2 2 -3 输出 3 说明 从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3 2) .算法思路
两种情况首位相连的和首位不相连的首尾相连的可以算最小的连续子数组得出sum-就是。注意整个数组都是最小的情况。 3算法步骤
1.读取输入数据包括环形数组的长度n和数组中的元素。 2.初始化变量sum为数组中所有元素的和。 3.创建两个数组dpmin和dpmax用于记录以当前位置为结束点的最小和最大连续子数组的和。 4.初始化dpmin和dpmax的第一个元素为数组的第一个元素。 5.初始化变量max为dpmax的第一个元素变量min为dpmin的第一个元素。 6.遍历数组从第二个元素开始 1更新dpmax[i]为当前元素nums[i]和nums[i]加上dpmax[i-1]的较大值。 2更新max为dpmax数组中的最大值。 7.遍历数组从第二个元素开始 1更新dpmin[i]为当前元素nums[i]和nums[i]加上dpmin[i-1]的较小值。 2更新min为dpmin数组中的最小值。 8.根据sum和min的比较结果判断环形数组是否包含整个数组。 1如果sum等于min则环形数组包含整个数组。将max作为结果。 2否则用sum减去min的结果与max比较取较大值作为结果。 9.输出结果。 4. 代码实例
package NiukeTest.动态规划;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class 环形数组的连续子数组最大值 {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static String[] lines;public static void main(String[] args) throws IOException {lines in.readLine().split( );int n Integer.parseInt(lines[0]);int[] nums new int[n];long sum 0;lines in.readLine().split( );for (int i 0; i n; i) {nums[i] Integer.parseInt(lines[i]);sum nums[i];}// 两种情况首位相连的和首位不相连的// 首尾相连的可以算最小的连续子数组得出sum-就是。int[] dpmin new int[n];int[] dpmax new int[n];dpmin[0] nums[0];dpmax[0] nums[0];long max dpmax[0];long min dpmin[0];for (int i 1; i n; i) {dpmax[i] Math.max(nums[i], nums[i] dpmax[i - 1]);max Math.max(max, dpmax[i]);}for (int i 1; i n; i) {dpmin[i] Math.min(nums[i], nums[i] dpmin[i - 1]);min Math.min(min, dpmin[i]);}long result;if (sum min) {result max;} else {result Math.max(max, sum - min);}out.println(result);out.flush();out.close();}
} 5. 总结
动规的状态分析很重要开几个状态是关键。 试题链接
