contiguous subarray with largest sum in an array (Maximum Subarray) | Runhe Tian...
source link: https://tianrunhe.wordpress.com/2012/08/03/contiguous-subarray-with-largest-sum-in-an-array-maximum-subarray/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
contiguous subarray with largest sum in an array (Maximum Subarray)
03 Aug 2012 2 Comments
by Runhe Tian in LeetCode Tags: Array, C++, Java
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.
Thoughts:
For each element in the array, we want to track the subarray with the largest sum ending here. And the largest of those largest sums is the result we need. So how do we track the largest sum ending at a particular position? We can keep adding up positive numbers. We can also add negative numbers as long as the sum would be less than 0. If it’s smaller than 0, we need to reset from this position by starting the sum from 0. In the above example, the largest sums ending at each position are [-2,1,-3,4,3,5,6,1,5]. Hence the largest sum is 6.
code (Java):
public class Solution {public int maxSubArray(int[] A) {int maxSumSoFar = Integer.MIN_VALUE;int maxSumEndingHere = 0;for(int num : A) {maxSumEndingHere = Math.max(maxSumEndingHere + num, num);maxSumSoFar = Math.max(maxSumSoFar, maxSumEndingHere);}return maxSumSoFar;}}Code (C++):
class Solution {public:int maxSubArray(int A[], int n) {int maxSumSoFar = INT_MIN;int maxSumEndingHere = 0;for(int i = 0; i < n; ++i) {maxSumEndingHere = max(maxSumEndingHere+A[i], A[i]);maxSumSoFar = max(maxSumSoFar, maxSumEndingHere);}return maxSumSoFar;}};Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK