Need advice - Kadane's algorithm vs Recursion method

[memepapa]

My Question - how should I learn more effectively?

1) just learn the most effective/simpler way of solving a code challenge?

or

2) study all the various ways of solving the same code challenge?

---

As I progress to learn from leetcode challenges, I stumble with different solutions.

for example, given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.


I find it a lot easier to understand Kadane's algorithm.

  #include<iostream>
using namespace std;

//Function to find maximum sum contiguous subarray in a given set of integers

int kadane(int nums[], int n)
{
	//stores maximum sum subarray found so far
	 
	int max_so_far = 0;
	 
	//stores the maximum sum of subarray ending at the current position

	int max_ending_here = 0;

	//traverse the given array

	for (int i = 0; i < n; i++)
	{
    	/* update maximum sum of subarray "ending" at index i (by adding the current element to maximum sum ending at previous index i-1) */

    	max_ending_here = max_ending_here + arr[i];
 
    	/* if maximum sum is negative, set it to 0 (which represents an empty sub-array) */
    	if(max_ending_here < 0)
    	{
        	max_ending_here = 0;
    	}
     	 
    	//update result if current subarray sum is found to be greater
    	if(max_so_far < max_ending_here)
    	{
        	max_so_far = max_ending_here;    
    	}
	return max_so_far;
}

int main()
{
 	int nums[] = {-2, -3, 4, -1, -2, 1, 5, -3};
 	int n = sizeof(nums)/sizeof(nums[0]);
 	cout << "Maximum sum contiguous subarray is "<<kadane(arr, n);
 	return 0;
}

Although I have been studying recursion daily for the past week, I'm still find it challenging how to write recursive codes.

I read that often iterative codes can be more effective than recursive codes, and programmers write recursive codes because it looks cleaner?


the following solution using recursive code is particularly confusing to me, and it took me thrice more effort to understand it than the Kadane's algo solution.

here's the recursive version

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
using std::max;

class Solution{
public:
    int globalMaxSum;
    int maxSubArray(vector<int> &nums, int n) {
        if (n ==1 ) return nums[0];
        int currMaxSum = max(nums[n-1], maxSubArray(nums, n-1) + nums[n-1]);
        globalMaxSum = max(globalMaxSum, currMaxSum);
        return currMaxSum;
    }

    int maxSubArray(vector<int> &nums) {
        globalMaxSum = nums[0];
        maxSubArray(nums, nums.size());

        return globalMaxSum;
    }
};

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};		// answer should be 6

    Solution test;
    cout << test.maxSubArray(nums) << endl;

    return 0;

}

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

int bestSubsequenceSum( const vector<int> &A )
{
   int sum = 0, lowsum = 0, best = 0;
   for ( int e : A )
   {
      sum += e;
      if ( sum < lowsum ) lowsum = sum;
      if ( sum - lowsum > best ) best = sum - lowsum;
   }
   return best;
}


int main()
{
   vector<int> A = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
   cout << bestSubsequenceSum( A );
}

[memepapa]

thanks lastchance,

now trying to understand your code

for ( int e : A )

this is a for-each loop?

which is a shorthand version of writing

for (int e = 0; e < sizeof(A)/sizeof(A[0]); e++)


so far so good?

[jonnin]

a vector is not an array -- you can use .size() if you want to know how many things are in it.
yes, the range based for loop syntax is a short hand of sorts.
It is really more like a form of pointer based loops, eg
something *sp = somestartposition;
for(; sp != someENDposition; sp++)
*sp.modify(value);

Although I have been studying recursion daily for the past week, I'm still find it challenging how to write recursive codes.

This is a difficult topic, and takes more than a week to absorb fully. Sure, simple functions are easy, but give it more time. Take a bit of time off and do some other learning, let this sit in your brain. Your brain is amazing, and it likes to work on understanding things 'offline'. After a break circle back and you may find it easier.

recursion, at the end of the function (tail-recursion) is equal to iterative code: the compiler knows how to rewrite this as a simple loop. If you do the recursion elsewhere in the function, it actually makes the function calls, which can be inefficient and can risk blowing out the call stack.

recursion does one thing, really. It provides you with a free stack data structure that you can use in creative ways without needing extra code. That gives you 2 main reasons to write recursive code, both of them relatively rare (one, using the free stack, and two, expressing an idea that is naturally recursive or that lends itself to significantly smaller code with recursion) and the third reason -- you like doing it or something, and use it when not necessary or helpful.

an example of a natural problem would be a recursive sequence, like factorials or fibonacchi, where a term is defined by the previous term(s). An example of example of using the stack is a maze solver, where if you get to a dead end, you pop back to the last decision and try another path. An example of not necessary is again a small (fit in int 64) factorial, which in real code would be a lookup table, not a computation of any kind.

Recursion as the best choice is rare. I would say < 10% of all problems fall into the 'don't need it, and even if could be done that way there is no reason to do so' category. Of that 10%, the vast (80%+) majority of those are very simple, one liners. The rest are where it is super useful and powerful, like array sorting. And of those, the majority again will be things that are been-there, done-that well known algorithms or following the pattern of one of those. A totally new problem with a new algorithm using recursion is a very rare thing. If you understand the recursion of sorting, tree processing, sequence generation, maze tracking, and maybe one or two advanced problems like 8 queens, you will be in really good shape.

[memepapa]

and i'm trying to compare your code

{
      sum += e;
      if ( sum < lowsum ) lowsum = sum;
      if ( sum - lowsum > best ) best = sum - lowsum;
   }
   return best;

to the Kadane's Algo i posted earlier.

max_ending_here = max_ending_here + arr[i];
 
    	/* if maximum sum is negative, set it to 0 (which represents an empty sub-array) */
    	if(max_ending_here < 0)
    	{
        	max_ending_here = 0;
    	}
     	 
    	//update result if current subarray sum is found to be greater
    	if(max_so_far < max_ending_here)
    	{
        	max_so_far = max_ending_here;    
    	}
	return max_so_far;
}

i can understand the part on " sum += e; "

but i'm having difficulty visualizing

if ( sum < lowsum ) lowsum = sum;
if ( sum - lowsum > best ) best = sum - lowsum;


should i go focus on learning dynamic programming to be better understand similar codes in future? it's a topic i have yet to get started on...

[lastchance]

for ( int e : A )
this is a for-each loop?

Effectively, yes - although, to be pedantic, a true for-each loop could probably be parallelised (guaranteed no side effects and hence no assumed order of calculation or disposition amongst processors) whereas this one is iterated through: "range-based for loop", invented (for c++) in C++11. It's taken as read in many languages, like Python, and not needed for languages that can do elemental operations, like Fortran or Python's numPy arrays.

It's not quite the same as the for ( int i = 0; i < A.size(); i++ ) form, because if you actually wanted to change the elements of A you would need to use references to them with an &:
for ( int &e : A )
and also you would have no (easy) means of accessing the other elements of A as you would with an index form.

but i'm having difficulty visualizing
if ( sum < lowsum ) lowsum = sum;
if ( sum - lowsum > best ) best = sum - lowsum;

Draw a graph of the cumulative sum. The best subsequence sum is the biggest overall change from a low to a high of that sum.



Apropos of nothing, and entirely out of curiosity, did you ever solve your compiler problem here:
https://www.cplusplus.com/forum/beginner/281892/#msg1219695

[memepapa]

thanks Jonin, well written and your explanation is helping me progress.

thanks lastchance, i haven't been able to solve the compiler problem on my macbook air's terminal


i could, however, get it compiled well on various online compilers

Additionally, i downloaded Clion and i could get it to compile properly locally on my macbook.

in other words, my mac's terminal is using a g++ compiler that has some inherent problems?