【动态规划】最大连续字串（Java实现）

文章目录

• • 1. 题目描述
  • 2. 算法思路
  • 3. 代码实现

1. 题目描述

• 给你一个整数数组nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
• 子数组是数组中的一个连续部分。

示例：

• 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

• 输出：6

  解释：连续子数组 [4,-1,2,1] 的和最大为 6。

2. 算法思路

方法 1：暴力求解法，使用两重循环，遍历遍历，然后求和，时间复杂度高
方法 2：动态规划DP，使用辅助数组b[i]表示包括下标i之前的最大连续子序列和，递推式可以通过

• b[i-1]+arr[i]：把arr[i]加入当前的连续子序列和
• arr[i]：从头开始计算子序列和

两者比较取最大，即为b[i]的值

3. 代码实现

import java.util.*;
/**
 * @Author 
 * @Date
 * @Description 最大连续字串
 */
public class MaximumSubarry {
    public static void main(String[] args) {
        int[] arr = {2,3,-9,3,2,1,-1,5,-9,1,2,3};
        int result1 = DPMaximumSubarry(arr);
        System.out.println("动态规划：最大联系字串长度和为"+result1);
        int result2 = BruteForceMaxSubarry(arr);
        System.out.println("暴力求解：最大联系字串长度和为"+result2);
    }
    /**
     * 动态规划求解
     * @param arr 需要求解的一维数据
     * @return 最大连续字串长度和
     */
    public static int DPMaximumSubarry(int[] arr){
        int sum =arr[0]; // 该方法最终返回结果
        int[] b = new int[arr.length]; // b[i]:以arr[i]结尾的最大子数组和
        b[0] = arr[0]; // 初始化第一个

        for(int i = 1; i < arr.length; i++){
            // 求解式
            b[i] = Math.max(b[i-1]+arr[i],arr[i]);
            // 更新答案
            if(b[i] > sum){
                sum = b[i];
            }
        }
        return sum;
    }

    /**
     * 暴力循环求解
     * @param arr 需要求解的一维数据
     * @return 最大连续字串长度和
     */
    public static int BruteForceMaxSubarry(int[] arr){
        int sum = Integer.MIN_VALUE;
        // 两个循环遍历起点i与终点j
        for(int i = 0;i < arr.length ;i++){
            for(int j = i;j< arr.length;j++){
                // 求解字串和
                int s = 0;
                for(int k = i; k <= j; k++){
                    s += arr[k];
                }
                sum = Math.max(sum,s);
            }
        }
        return sum;
    }
}

输出：