We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Attention ! One correction needs to be made for this wiki solution when array has negative value, max_ending_here must be initialized to 0, while max_so_far must be initialized to either Integer.MIN_VALUE or arr[0], instead of 0, in order to handle negative values for calculating max continuous subarray.
ps. I just corrected wiki solution.
My working solution in java:
static void printMaxSum(int[] arr){
//1) For max continuous sub array
int max_ending_here = 0;
int max_so_far = Integer.MIN_VALUE;
/*OR int max_so_far = arr[0];*/
for(int x : arr){
max_ending_here = Math.max(x, max_ending_here + x);
max_so_far = Math.max(max_so_far, max_ending_here);
}
System.out.print(max_so_far);
//2) For max non-continuous sub array, order doesn't matter
Arrays.sort(arr);
int sum = 0;
//if there is none positive value in entire array
if(arr[arr.length-1] <= 0)
sum = arr[arr.length - 1];
//accumulate all positive values in entire array
else{
for(int x : arr){
if(x > 0)
sum += x;
}
}
System.out.println(" " + sum);
}
The goal of this problem for computer scientists would be to compute it optimally without any unneeded steps. Your algorithm seems good! But also the Wikipedia algorithm seems good the way it was.
If you are already assigning A[0] then you should simply initialise both max_ending_here and max_so_far to A[0]. Then you will iterate over the remainder of the list from A[1:].
If you follow your algorithm above, and iterate over the entire array A[:], you will see that you are making an unnecessary reassignment for the first element.
Assuming you made the revision on 15 February 2016, you caused the algorithm to have a slight error due to Wikipedia having A[1:], not A[:] as you have above, and you also failed to describe why you made the changes to describe why you made them. I think that's why your edits were rolled back as "Vandalism". https://en.wikipedia.org/w/index.php?title=Maximum_subarray_problem&diff=next&oldid=705159845
Looks good to me. But you haven't shown how you update pb so I can't understand completely.
One note, it seems to me that pb=(b>pb)?b:pb; is another way to write pb=max(b,pb);. I note that using algebra, pb+c>c is equivalent to pb>0, which is slightly more efficient. Similarly pb+c>pb is the same as c>0.
On the other hand, when is is not the best sum. you will need to update pb. When there are all negative elements, pb is undefined by the problem statement; either pb = 0 because the shortest array is 0 length, or it's equal to the smallest element, because the shortest array is 1 length.
I think that you used the second definition, right?
For noncontiguous with at least one positive element, similar to @maximshen's solution above, just needs to sum all positive elements. That one is easy, it looks like: for(int x:arr) { b = b + (c>0)?c:0; }
I said that "When there are all negative elements, pb is undefined by the problem statement". This is true only for the general case (see the Wikipedia article), but the HackerRank problem stated the second method, in which at least one element must be selected, so if all elements are negative, it's the max value of all elements.
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0)
return 0;
int maxSum = array[0];
int arr = array[0];
for (int i = 1; i < array.length; i++) {
yeah kadane's algorithm is a very well known solution for subarray sum problem..what do u want to ask? one more thing in this u will not be able to find the answer if all the inputs are negative so a little modification is required..
Sorting the array is not necessary here and will actually become the bottle neck in your solution as the Java.utils.Arrays uses quicksort. This makes your solution O(n^2) in the worst case. You could simply put this line inside of your for loop to determine the max sum of noncontiguous subarray:
sum = Math.max(arr[j], sum + (arr[j] > 0 ? arr[j] : 0) );
This would uphold the O(n) efficiency of Kadane's algorithm.
i came up with a much simpler way to write out a solution, and i'll post an explanation here:
msf is the maximum sum so far, and mfa is the maximum number from the array
ans is just where both answers are stored
you can first set both the answers and the msf and mfa to the lowest possible number, to avoid negatives getting in the way, as the constraints do say the numbers can go to the negatives
you can calculate the maximum sum so far by using max(a, msf+a), a being the new element added to the array. this can be demonstrated as asking yourself a question:
will the maximum sum so far become bigger if i start a new contiguous subarray, or will it become bigger if i continue the contiguous subarray we have previously created?
getting the maximum element from the array is easy, just a simple max(mfa, a). you can set the answer to the maximum subarray question as the maximum of the maximum subarray previously created, or the subarray created just now as another element was added. then you can set the answer to the maximum subsequence question as the maximum of the maximum subsequence previously created, or the maximum element in the array (gets rid of dealing with an array of fully negative numbers), or the previous maximum subsequence plus the new element, which will be chosen if the new element is positive only.
code is as follows:
#include<bits/stdc++.h>usingnamespacestd;#define ll long long#define ull unsigned long long#define uset unordered_set#define umap unordered_mapconstintmxN=1e5;lln,a,ans[2],msf,mfa;intmain(){ios::sync_with_stdio(0);cin.tie(0);intt;cin>>t;while(t--){cin>>n;msf=-1e18,mfa=-1e18;ans[0]=-1e18,ans[1]=-1e18;for(inti=0;i<n;++i){cin>>a;msf=max(a,msf+a);mfa=max(mfa,a);ans[0]=max(ans[0],msf);ans[1]=max({ans[1],mfa,ans[1]+a});}cout<<ans[0]<<" "<<ans[1]<<"\n";}}
The Maximum Subarray
You are viewing a single comment's thread. Return to all comments →
Attention ! One correction needs to be made for this wiki solution when array has negative value, max_ending_here must be initialized to 0, while max_so_far must be initialized to either Integer.MIN_VALUE or arr[0], instead of 0, in order to handle negative values for calculating max continuous subarray.
ps. I just corrected wiki solution.
My working solution in java:
The goal of this problem for computer scientists would be to compute it optimally without any unneeded steps. Your algorithm seems good! But also the Wikipedia algorithm seems good the way it was.
If you are already assigning A[0] then you should simply initialise both
max_ending_hereandmax_so_fartoA[0]. Then you will iterate over the remainder of the list fromA[1:].If you follow your algorithm above, and iterate over the entire array
A[:], you will see that you are making an unnecessary reassignment for the first element.Assuming you made the revision on 15 February 2016, you caused the algorithm to have a slight error due to Wikipedia having
A[1:], notA[:]as you have above, and you also failed to describe why you made the changes to describe why you made them. I think that's why your edits were rolled back as "Vandalism". https://en.wikipedia.org/w/index.php?title=Maximum_subarray_problem&diff=next&oldid=705159845Hi, took a different approach.
wanted to know if it is DP
for contiguous case:
b=(pb+c>c)?pb+c:c;
for noncontiguous case:
b=(pb+c>pb)?max(pb+c,c):max(pb,c);
where:
b-best sum
pb-previousBest
c-current element
Looks good to me. But you haven't shown how you update pb so I can't understand completely.
One note, it seems to me that
pb=(b>pb)?b:pb;is another way to writepb=max(b,pb);. I note that using algebra,pb+c>cis equivalent topb>0, which is slightly more efficient. Similarlypb+c>pbis the same asc>0.On the other hand, when is is not the best sum. you will need to update pb. When there are all negative elements, pb is undefined by the problem statement; either pb = 0 because the shortest array is 0 length, or it's equal to the smallest element, because the shortest array is 1 length.
I think that you used the second definition, right?
For noncontiguous with at least one positive element, similar to @maximshen's solution above, just needs to sum all positive elements. That one is easy, it looks like:
for(int x:arr) { b = b + (c>0)?c:0; }I said that "When there are all negative elements, pb is undefined by the problem statement". This is true only for the general case (see the Wikipedia article), but the HackerRank problem stated the second method, in which at least one element must be selected, so if all elements are negative, it's the max value of all elements.
Hi,
yes I used an array to keep track of pb, and then selected the max from that array to get the best possible sum.
I do agree the expressions can be re-written to improve efficiency. I skipped that to keep it simple.
Thanks,
peace ..\/,
public int FindGreatestSumOfSubArray(int[] array) { if(array.length==0) return 0; int maxSum = array[0];
int arr = array[0];
for (int i = 1; i < array.length; i++) {
yeah kadane's algorithm is a very well known solution for subarray sum problem..what do u want to ask? one more thing in this u will not be able to find the answer if all the inputs are negative so a little modification is required..
Sorting the array is not necessary here and will actually become the bottle neck in your solution as the Java.utils.Arrays uses quicksort. This makes your solution O(n^2) in the worst case. You could simply put this line inside of your for loop to determine the max sum of noncontiguous subarray:
This would uphold the O(n) efficiency of Kadane's algorithm.
Such Cleanly written code !!!
Hey! Can you write it in C++?
How do I call your solution?
When I call your solution in main what should I do? I am new to programming.
i came up with a much simpler way to write out a solution, and i'll post an explanation here:
msf is the maximum sum so far, and mfa is the maximum number from the array
ans is just where both answers are stored
you can first set both the answers and the msf and mfa to the lowest possible number, to avoid negatives getting in the way, as the constraints do say the numbers can go to the negatives
you can calculate the maximum sum so far by using
max(a, msf+a), a being the new element added to the array. this can be demonstrated as asking yourself a question:will the maximum sum so far become bigger if i start a new contiguous subarray, or will it become bigger if i continue the contiguous subarray we have previously created?
getting the maximum element from the array is easy, just a simple
max(mfa, a). you can set the answer to the maximum subarray question as the maximum of the maximum subarray previously created, or the subarray created just now as another element was added. then you can set the answer to the maximum subsequence question as the maximum of the maximum subsequence previously created, or the maximum element in the array (gets rid of dealing with an array of fully negative numbers), or the previous maximum subsequence plus the new element, which will be chosen if the new element is positive only.code is as follows:
7 2 -1 2 3 4 -5 1 for this test case ans has to come 10 11, but it comes 10 12
Your solution is O(NlogN) by the sort algorithm, with dynamic programming is faster because it is linear.
I've done the same using **Kadane's **algorithm