最大子数组和

public class Demo02

{

    public static void main(String[] args)

    {

        int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int dan = dan(arr);

        System.out.println(dan);

    }

    public static int dan(int nums[])

    {

        int n = nums.length;

        // 创建一个长度为 n 的数组

        int[] dp = new int[n];

        // 将第一个元素赋值给 dp 的第一个位置中

        dp[0] = nums[0];

        // 将 dp 数组的第一个元素的值赋值到 max 作为最大值

        int max = dp[0];

        // 因为已经将第一个元素赋值到了 dp 数组中，所以只需要从 1 开始遍历让 dp 的第一个元素和 nums 的后一个元素进行相加然后比较 nums 原来后一个元素的值取较大值

        for (int i = 1; i < n; i++)

        {

            //dp 数组中的前一个元素 与 nums 数组的后一个元素相加，nums 后一个元素 比较两个值的最大值赋值到 dp 数组的后一个位置

            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

            //max 值与 dp 后一个元素的值也就是上面获取的最大值比较将最大值赋值给 max

            max = Math.max(max, dp[i]);

        }

        // 返回最大值

        return max;

    }

}