首页 > 代码库 > leetcode--Maximum Subarray

leetcode--Maximum Subarray

2024-07-07 06:40:17   222人阅读

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Solution {
    /**
     * This program is an implementation of divide-and-conquer method
     * @param A --an array of integer
     * @return the maximum sum of a subarray
     * @author Averill Zheng
     * @version 2014-06-04
     * @since JDK 1.7
     */
    public int maxSubArray(int[] A) {
        return maxSubArrayHelper(A, 0, A.length);
    }
    /**
     * The function is used to find the maximum sum of a contiguous subarray between index i (inclusive) and j
     * (exclusive).
     * @param A --an integer array.
     * @param i --start index which is included.     
     * @param j --end index which is exclusive.
     * @return int --maximum sum of a contiguous subarray.
     */
    private int maxSubArrayHelper(int[] A, int i, int j){
        int max = Integer.MIN_VALUE;
        if(j > i){
            if(j == i + 1)
                max = A[i];
            else{
                int mid = i + (j - i) / 2;
                int leftMax = maxSubArrayHelper(A, i, mid);
                int rightMax = maxSubArrayHelper(A,mid, j);
                int crossMax = crossMax(A, i, j, mid);
                max = Math.max(Math.max(leftMax, crossMax), rightMax);
            }
        }
        return max;
    }
    private int crossMax(int[] A, int i, int j, int mid){
        //[i,mid) is the first half and [mid, j) is the second half
        //both of them contains at least one element
         
        //left max
        int leftMax = A[mid - 1];
        int leftSum = A[mid - 1];
        for(int k = mid - 2; k > i - 1; --k){
            leftSum += A[k];
            leftMax = (leftMax < leftSum) ? leftSum : leftMax;
        }
         
        //right max
        int rightMax = A[mid];
        int rightSum = A[mid];
        for(int k = mid + 1; k < j; ++k){
            rightSum += A[k];
            rightMax = (rightMax < rightSum) ? rightSum : rightMax;
        }
        return leftMax + rightMax;
    }
}

　　


联系
我们