提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

连续子数组的最大和

2023-02-18 16:36:15 时间

题目：

 

 

 

思路：

先是说一说对这道题的理解吧，这题要么采用的是暴力破解方法，采用双循环的方式。
通过一层循环，决定起始位置，然后不断循环从起始位置加起用于存储最大值。
或者采用动态规划，寻找出规律F(N) = F(N-1) + A[N]
这种方法的时间复杂度为O（N），空间复杂度为O(N)。

代码示例：

public class Solution {
 
    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};
        int result = FindGreatestSumOfSubArray(arr);
        System.out.println(result);
    }
 
    public static int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        //用于存储动态规划的结果数组
        int[] currentsum = new int[len];
        currentsum[0] = array[0];
        int maxsum = array[0];
        for (int i = 1; i < len; i++) {
            //利用F(N) = F(N-1) + A[N] 来记录以第i个数字结尾的子数组的最大和
            //此外要记得如果F(N)<0,则下一次会直接拿A[N]赋值进去，因为如果是负数了，那么与后面的数相加只会起到变小作用
            //此外，另用一个变量存储遇到的最大的连续子数组的和。
            if (currentsum[i - 1] > 0) {
                currentsum[i] = currentsum[i - 1] + array[i];
            } else {
                currentsum[i] = array[i];
            }
 
            if (currentsum[i] > maxsum) {
                maxsum = currentsum[i];
            }
        }
        return maxsum;
    }
}

相关文章