LeetCode:53.Maximum Subarray

Posted on Edited on In

Problem Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Wrong Code

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    int sum = nums[0];
    for (int i=0; i<nums.length;i++){
        int temp = nums[i];
        for (int j=i+1; j<nums.length; j++){
            temp += nums[j];
            if(temp>sum){
                sum = temp;
            }
        }
    }
    return sum;
}

Error Information

Input [-2,1]
Output -1
Expected 1

Wrong Thinking

My program will stop entering the second layer loop when i = nums.length-1 which refer to the last digit. In this situation, when the sum has already been decided and cannot be changed anymore. So I have take this situation into account.

Correct Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxSubArray(int[] nums) {
        int sum = nums[0];
        for (int i=0; i<nums.length;i++){
            int temp = nums[i];
            if(temp>sum){
                sum = temp;
            }
            for (int j=i+1; j<nums.length; j++){
                temp += nums[j];
                if(temp>sum){
                    sum = temp;
                }
            }
        }
        return sum;
    }

Review

Just take the situation into account and add another statement in the first layer loop

Better Code

Dynamic Programming

Usually problem about optimization can be solved by dynamic programming. As for DP, the most important thing is finding the recursion within the problem.
In terms of this problem, we define the problem as maxSubArray(int A[],int i). Assume we have the result of problemmaxSubArray(A, i-1), we can get a equation as:
maxSubArray(A,i) = maxSubArray(A,i-1)>0?maxSubArray(A,i-1):0+A[i];
In short, if you know the solution of the maxSubArray which ends up with index i-1, there are two choices: 1. Start a new subarray from index i; 2. Expand the previous subarray with index i.

Code

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
        int n = nums.length;
        int res = nums[0];
        int cmp = res;
        for(int i = 1; i < n; i++)
        {
            int temp = cmp;
            res = Math.max(res+nums[i],nums[i]);
            cmp = Math.max(res, temp);
        }
        return cmp;
}

res: biggest value if subarray ends up with nums[i]
cmp: biggest value so far