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. 这题是一道经典的dp问题，我们可以很容易的得到其dp方程，假设dp[i]是数组a [0, i]区间最大的值，那么 dp[i + 1] = max(dp[i], dp[i] + a[i + 1]) 代码如下: 1. class Solution { 2. public: 3. int maxSubArray(int A[], int n) { 4. int sum = 0; 5. int m = INT_MIN; 6. 7. for(int i = 0; i < n; i++) { 8. sum += A[i]; 9. m = max(m, sum); 10. //如果sum小于0了，将sum重置为0，从i + 1再次开始计算 11. if(sum < 0) { 12. sum = 0; 13. } 14. } 15. 16. return m; 17. } 18. };

虽然这道题目用dp解起来很简单，但是题目说了，问我们能不能采用divide and conquer的方法解答，也就是二分法。 假设数组A[left, right]存在最大区间，mid = (left + right) / 2，那么无非就是三中情况： 1. 最大值在A[left, mid - 1]里面 2. 最大值在A[mid + 1, right]里面 3. 最大值跨过了mid，也就是我们需要计算[left, mid - 1]区间的最大值，以及[mid + 1, right]的最大值，然后加上mid，三者之和就是总的最大值

我们可以看到，对于1和2，我们通过递归可以很方便的求解，然后在同第3的结果比较，就是得到的最大值。 代码如下: 1. class Solution { 2. public: 3. int maxSubArray(int A[], int n) { 4. return divide(A, 0, n - 1, INT_MIN); 5. } 6. 7. int divide(int A[], int left, int right, int tmax) { 8. if(left > right) { 9. return INT_MIN; 10. } 11. 12. int mid = left + (right - left) / 2; 13. //得到子区间[left, mid - 1]最大值 14. int lmax = divide(A, left, mid - 1, tmax); 15. //得到子区间[mid + 1, right]最大值 16. int rmax = divide(A, mid + 1, right, tmax); 17. 18. tmax = max(tmax, lmax); 19. tmax = max(tmax, rmax); 20. 21. int sum = 0; 22. int mlmax = 0; 23. //得到[left, mid - 1]最大值 24. for(int i = mid - 1; i >= left; i--) { 25. sum += A[i]; 26. mlmax = max(mlmax, sum); 27. } 28. 29. sum = 0; 30. int mrmax = 0; 31. //得到[mid + 1, right]最大值 32. for(int i = mid + 1; i <= right; i++) { 33. sum += A[i]; 34. mrmax = max(mrmax, sum); 35. } 36. 37. tmax = max(tmax, A[mid] + mlmax + mrmax); 38. return tmax; 39. } 40. };

Maxmimum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6. 这题是求数组中子区间的最大乘积，对于乘法，我们需要注意，负数乘以负数，会变成正数，所以解这题的时候我们需要维护两个变量，当前的最大值，以及最小值，最小值可能为负数，但没准下一步乘以一个负数，当前的最大值就变成最小值，而最小值则变成最大值了。 我们的动态方程可能这样： 1. maxDP[i + 1] = max(maxDP[i] * A[i + 1], A[i + 1], minDP[i] * A[i + 1]) 2. minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1], maxDP[i] * A[i + 1] 3. dp[i + 1] = max(dp[i], maxDP[i + 1])

这里，我们还需要注意元素为0的情况，如果A[i]为0，那么maxDP和minDP都为0，我们需要从A[i + 1]重新开始。 代码如下: 1. class Solution { 2. public: 3. int maxProduct(int A[], int n) { 4. if(n == 0){ 5. return 0; 6. } else if(n == 1) { 7. return A[0]; 8. } 9. 10. int p = A[0]; 11. int maxP = A[0]; 12. int minP = A[0]; 13. for(int i = 1; i < n; i++) { 14. int t = maxP; 15. maxP = max(max(maxP * A[i], A[i]), minP * A[i]); 16. minP = min(min(t * A[i], A[i]), minP * A[i]); 17. p = max(maxP, p); 18. } 19. 20. return p; 21. } 22. };