转载

最大连续子数组和

最大连续子数组和(POJ1050)

最大子序和,可以简单地用基本的编程逻辑解决。

但这道问题,其实是一道动态规划的问题

  • 分析

    F ( i ) F(i) 是以元素arr[i]结尾的连续子数组的最大值(arr是原数组),

    则以下公式成立
    F ( i ) = F ( i ? 1 ) + a r r [ i ]     i f   F ( i ? 1 ) > = 0 F ( i ) = a r r [ i ]                      i f    F ( i ? 1 ) < 0 F(i) = F(i-1) + arr[i] \ \ \ if\ F(i-1) >= 0 \\ F(i) = arr[i] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if \ \ F(i-1) <0
    这是一个动态规划的递推式,满足动态规划的两个重要特征,

    最优子结构:原问题最优解包含子问题的最优解

    子问题重叠:计算原问题的时候,会反复计算某些子问题的解

    最大连续子数组和,就是找最大的 F ( i ) F(i) ,即找以那个元素结尾的连续数组值最大

  • 实例leetcode 53

    AC代码 (代码为了节省空间,改变了元素的值来存储对应元素的F(i))

    class Solution {
        public int maxSubArray(int[] nums) {
            
            if(nums.length <= 0) return 0;
            
            int maxValue = nums[0];
            
            for(int i=1; i<nums.length; i++) {
                if(nums[i-1] >= 0) nums[i] += nums[i-1];
                
                if(maxValue < nums[i]) maxValue = nums[i];
            }
            return maxValue;
        }
    }
    
    
  • 实例POJ 1050

    AC代码(主要的难点是想到将二维的矩阵转化到一维求解)

    参考链接POJ1050 子矩阵最大和

    import java.util.Scanner;
    import java.io.File;
    import java.io.FileNotFoundException;
    
    public class Main{
        public static void main(String args[]) {
            try{
                Scanner scanner = new Scanner(System.in);
    
                int n = scanner.nextInt(); int [][]arr = new int[n][n];
    
                for(int i = 0; i < n; i++)
                    for(int j = 0; j < n; j++)
                        arr[i][j] = scanner.nextInt();
    
                int maxValue = arr[0][0];
    
                for(int i = 0; i < n; i++) {
                    int []arrSum = new int[n];
                    for(int m = 0; m < n; m++) arrSum[m] = 0;
                    for(int j = i; j < n; j++) {
                        for(int k = 0; k < n; k++) arrSum[k] += arr[j][k];
                        maxValue = maxValue < maxSubArray(arrSum) ? maxSubArray(arrSum):maxValue;
                    }
                }   
                System.out.println(maxValue);  
            }catch(Exception e) {
                e.printStackTrace();
            }
        }
    
         public static int maxSubArray(int[] nums) {
            
            if(nums.length <= 0) return 0;
            
            int maxValue = nums[0];
    
            int dp[] = new int[nums.length]; dp[0] = nums[0];
            
            for(int i=1; i<nums.length; i++) {
                if(dp[i-1] >= 0) dp[i] = dp[i-1] + nums[i];
                else dp[i] = nums[i];
    
                if(maxValue < dp[i]) maxValue = dp[i];
            }
            return maxValue;
        }
    }
    
正文到此结束
本文目录