【算法】最大子数组和的动态规划算法，Java实现

迷南。 2022-09-10 12:07 165阅读 0赞

import java.util.Random;
    
    public class MainClass {
        public static void main(String[] args) {
            int[] array = new int[10];
    
            //生成随机测试数据，数据集里面必须有正有负。
            for (int i = 0; i < array.length; i++) {
                Random random = new Random();
                array[i] = (int) (Math.random() * 10) * (random.nextBoolean() ? 1 : -1);
            }
    
            //打印数据集
            System.out.println("测试的随机数组:");
            for (int n : array) {
                System.out.print(n + " ");
            }
    
            System.out.println("\n最大子数组和:");
            System.out.println(maxSub(array));
        }
    
        //最大子数组和的动态规划算法
        public static int maxSub(int[] array) {
            int retSum = 0;
    
            int sum = 0;
            int tempSum = 0;
    
            for (int i = 0; i < array.length; i++) {
                if (sum > 0) {
                    sum = sum + array[i];
    
                    if (sum > tempSum) {
                        tempSum = sum;
                    }
                } else {
                    sum = array[i];
                }
    
                retSum = Math.max(retSum, sum);
            }
    
            return retSum;
        }
    }

测试几轮数据集输出如下：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_17_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_16_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_15_color_FFFFFF_t_70_g_se_x_16][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e8f18c125ea942a59e3dc27ff08e5683.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c84500ed57564fe19847d77e04634844.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/647684f6a9f4455d84ec41fb11e58b39.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_17_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/95f5f53dbd3d4374a48e3644eaaa21a0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAemhhbmdwaGls_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/9f788bdb001d44ff99200e3f59612142.png