Maximum Subarray

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.

思路一

O(N^3)时间复杂度，超时

 1 public class Solution {
 2     public int maxSubArray(int[] A) {
 3         int maxValue = 0;
 4         for(int i = 0; i < A.length; i++){
 5             for(int j = 0; j < A.length; j++){
 6                 int sum = 0;
 7                 for(int k = i; k <= j; k++){                //计算sum
 8                     sum += A[k];
 9                 }//for
10                 maxValue = maxValue > sum ? maxValue : sum;    //更新maxValue
11             }//for
12         }//for
13         
14         return maxValue;
15     }
16 }

思路二：

O(N^2)时间复杂度，超时，ps:c++实现一样超时

 1 public class Solution {
 2     public int maxSubArray(int[] A) {
 3         int maxValue = A[0];
 4         for(int i = 0; i < A.length; i++){
 5             int sum = A[i];
 6             for(int j = i + 1; j < A.length; j++){                
 7                 sum += A[j];
 8                 maxValue = maxValue > sum ? maxValue : sum;
 9             }//for
10         }//for
11         
12         return maxValue;
13     }
14 }

思路三：

DP，O(n)时间复杂度，可以AC

遍历数组，对于任意元素A[i]，只有两种可能，放到[k...i - 1]中，不放到[k...i - 1]中

1.放：此时sum,即连续子串的和为sum(A[k...i])

2.不放：此时sum,即连续子串的和为sum(A[i])

if(sum(A[k...i]) > sum(A[i])) 放A[i]，否则不放A[i],从A[i]开始计算sum

注意站在A[i]的角度去想

 1 public class Solution {
 2     public int maxSubArray(int[] A) {
 3         int maxValue = A[0];
 4         int sum = A[0];
 5         for(int i = 1; i < A.length; i++){
 6             int temp = sum + A[i];
 7             sum = temp > A[i] ? temp : A[i];
 8             maxValue = maxValue > sum ? maxValue : sum;
 9         }
10         
11         return maxValue;
12     }
13 }

思路四：分治法待续...

ps:相同代码，c++的时间确实要比java块很多