算法题--最大子串和与斐波那契数列 2021-03-01 21:27 > 最大子串和算法是某大厂一面。这个批注是后来统一加的,忘记当时是哪家公司了。 ### 最大子串和算法: 给出一个数字数组,有正数和负数,求其所有连续子串中和最大的值。 例如:{-3,1,2,0,-5,6,2} 其中连续子串是指:{-3},{-3,1},{-3,1,2}...这种,其连续子串中和最大的是8,对应的子串为{6,2} ```java package com.demo; /** * @author: HanXu * on 2021/3/1 * Class description: 最大子串和: 存在连续的字串使其在该数组的所有字串中元素的和最大。时间复杂度:O(n) * 例如 [-2,1,-3,4,-1,2,1,-5,4] 最大子串和为6:4,-1,2,1 */ public class MaxSum { public static void main(String[] args) { int[] arr = {-3,4,5,1,-7,2,-6,2,-3,7}; int[] brr = {100,4,5,1,-90,99,10,2,-130,7}; int[] crr = {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(maxSumGreedy(arr)); System.out.println(maxSumDP(arr)); System.out.println(maxSumViolencePro(arr)); } /** * 贪心算法:若当前指针所指元素之前的和小于0,则丢弃当前元素之前的数列。因为那些数列对最大和的子串没有帮助(负数,加上也是帮倒忙) * @param arr * @return */ public static int maxSumGreedy(int[] arr) { int max; int maxExplorer = max = arr[0]; for (int i = 1; i < arr.length; i++) { maxExplorer = Math.max(maxExplorer + arr[i], arr[i]); max = Math.max(maxExplorer, max); } return max; } //更好理解的版本:如果sum大于0的话,说明对后面的有帮助,加上;否则对后面的没有帮助 public static int maxSumGreedy2(int[] arr) { int max; int sum = max = arr[0]; for (int i = 1; i < arr.length; i++) { //这个if else 其实就是上面的 maxExplorer = Math.max(maxExplorer + arr[i], arr[i]); if (sum > 0) { sum += arr[i]; } else { sum = arr[i]; } max = Math.max(sum, max); } return max; } //带索引版本 private static int maxSumGreedy3(int[] arr) { int len = arr.length; if (len == 0) { return 0; } if (len == 1) { return arr[0]; } int tempMax = arr[0]; int max = tempMax; int beginIndex = 0; int endIndex = 0; for (int i = 1; i < arr.length; i++) { if (tempMax > 0) { tempMax = tempMax + arr[i]; if (tempMax > max) { max = tempMax; endIndex = i; } } else { // 若tempMax不是正数,那么不管后面的值为何值,加上tempMax之后都不会增加,也即“子串和”不会再增大,所以我们应该舍弃当前的tempMax,用后面的值来当tempMax tempMax = arr[i]; if (tempMax > max) { max = tempMax; beginIndex = endIndex = i; } } } System.out.println("index范围:[" + beginIndex + "," + endIndex + "]"); return max; } /** * 动态规划:若前一个元素大于0,则将其加到当前元素上。相当于求arr[i,j]时,倒着求,先求了arr[j],再求arr[j - 1]。倒着求能利用之前算过(子问题)的结果。 * 时间复杂度:O(n) 空间复杂度:O(1) * @param arr * @return */ public static int maxSumDP(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i - 1] > 0) { arr[i] += arr[i - 1]; } max = Math.max(max, arr[i]); } return max; } /** * 暴力求解,遍历每个子串,依次判断是否和最大. 时间复杂度O(n^3) 空间复杂度O(1) * @param arr * @return */ private static int maxSumViolence(int[] arr) { int max = arr[0]; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { int sum = sum(arr, i, j); if (sum > max) { max = sum; } } } return max; } /** * 对暴力求解的优化:使用sum变量储存arr[i,j]的和,仅仅是将上述sum函数优化调了。时间复杂度O(n^2) * 为什么可以优化掉,因为两次for循环就已经能遍历到所有子串了,只需要使用中间变量记录其中每次变化时的tempMax和max比较即可。 * @param arr * @return */ private static int maxSumViolencePro(int[] arr) { int max = arr[0]; for (int i = 0; i < arr.length; i++) { int sum = 0; for (int j = i; j < arr.length; j++) { sum += arr[j]; if (sum > max) { max = sum; } } } return max; } /** * 求和 * @param arr * @param i * @param j * @return */ private static int sum(int[] arr, int i, int j) { int sum = 0; for (int k = i; k <= j; k++) { sum += arr[k]; } return sum; } } ``` ### 斐波那契数列: ```java package com.demo; /** * @author: HanXu * on 2021/3/1 * Class description: 斐波那契数列: 第一项、第二项为1,其余项的值为它前两项之和 * 1 1 2 3 5 8 13 21 34 55 89 * */ public class Fibo { public static void main(String[] args) { System.out.println(fibo(11)); } /** * 求斐波那契数列第n项的值 * @param n * @return */ private static int fibo(int n) { if (n == 1 || n == 2) { return 1; } int pre = 1; int current = 1; int temp; for (int i = 2; i < n; i++) { temp = current; current = pre + current; pre = temp; } return current; } } ``` 以上两个算法的共同特点都是使用动态规划思想解决的。当然也能使用递归解决,我感觉动态规划的本质就是“优化的递归”,因为递归频繁创建函数太消耗空间,且递归过程中走了很多已经走过的路。所以动态规划就是将她优化一下。要解决当前问题,必须解决简化后的子问题,又将子问题的结果保存起来以备解决后面问题使用。 --- 后续应该会出一篇详细的动态规划的文章,到时候过来把这句话删掉,嗯... --END--
发表评论