首页 > 代码库 > LeetCode "Maximum Subarray"
LeetCode "Maximum Subarray"
Very classic problem. You can brush up your DP and Searching skills.
DP:
class Solution {public: int maxSubArray(int A[], int n) { // dp[i + 1] = max(dp[i] + A[i], A[i]); //int start = 0, end = 0; int max = A[0]; int sum = A[0]; for (int i = 1; i < n; i++) { if (A[i] >(sum + A[i])) { sum = A[i]; //if (sum > max) start = i; } else { sum = (sum + A[i]); //if (sum > max) end = i; } max = sum > max ? sum : max; } return max; }};
Equation: DP[i + 1] = max(DP[i] + A[i + 1], A[i + 1]). In case subarray location is needed, please check the commented lines.
And it is brand new to me as a rookie that it can also be solved by binary search ! We get 3 values: result of 1st half, result of 2nd half, and 3rd is the cross boundary case:
class Solution {public: int bigger(int a, int b) { return a > b ? a : b; } int solve(int A[], int start, int end) { if (start == end) return A[start]; int mid = start + (end - start) / 2; int leftMax = solve(A, start, mid); int rightMax = solve(A, mid + 1, end); // cross boundary? int sum0 = A[mid], cMaxL = A[mid]; for (int i = mid - 1; i >= start; i--) { sum0 += A[i]; cMaxL = bigger(sum0, cMaxL); } int sum1 = A[mid + 1], cMaxR = A[mid + 1]; for (int i = mid + 2; i <= end; i++) { sum1 += A[i]; cMaxR = bigger(sum1, cMaxR); } return bigger(bigger(leftMax, rightMax), cMaxL + cMaxR); } int maxSubArray(int A[], int n) { return solve(A, 0, n-1); }};
Deserve to revise later !
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。