Given an array that is not sorted. Find the largest sum that is made by adding the elements in the array that are contiguous.
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Method 1: Dynamic Programming:
In this method we take 2 new variables to store the “max” and “current_max”.
current_max will be the total of each element in the array, and we compare it with “max”. If the current_max is greater than max, then we update the max variable.
Method 2: Divide and Conquer:
Will be updated shortly
Solution in C++
#include<iostream> #include<string> #include<set> #include<vector> using namespace std; int get_max_sub_array_method_1(vector<int> &array) { int current_sum = 0; int max_sum = INT_MIN; for (int num : array) { current_sum += num; max_sum = max(max_sum, current_sum); if (current_sum < 0) { current_sum = 0; } } return max_sum; } int main() { vector<int> array = {-2,1,-3,4,-1,2,1,-5,4}; cout<<"The given array is : "<<endl; for (int i = 0; i < array.size(); i++) { cout <<array[i] << " "; } cout<<endl; cout<<"The maximum sum of continuous array is = "<<get_max_sub_array_method_1(array)<<endl; }
Output:
The given array is : -2 1 -3 4 -1 2 1 -5 4 The maximum sum of continuous array is = 6
Shubham Somu
/**
* Given an array, find the continuous sub array that has the largest sum, return the sum. 2 solutions in C++
*
* Input: [-2,1,-3,4,-1,2,1,-5,4],
*
* Output: 6
*
* Explanation: [4,-1,2,1] has the largest sum = 6.
*/
/**
* @author = Shubham
*/
package tele;
import static java.lang.System.out;
public class Que93 {
static int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
public static void main(String[] args){
out.println(subArray(arr.length));
}
static int subArray(int mainLen ){
int semiMax = arr[0];
int fullMax = arr[0];
for(int i=1; i max(1,-1) = 1
* fullMax = max(1,-2) = 1
*
* 2nd Iteration(a[2])
* semiMax = max (-3, (1 + (-3) )) ==> max(-3,-2) = -2
* fullMax = max(-2,1) = 1
*
* 3rd Iteration(a[3])
* semiMax = max (4, ( (-2) + 4) ==> max(4,2) = 4
* fullMax = max(4,1) = 4
*
* 4th Iteration(a[4])
* semiMax = max (-1, (4 + (-1) + 4 )) ==> max(-1,3) = 3
* fullMax = max(3,4) = 4
*
* 5th Iteration(a[5])
* semiMax = max (2, (2 + 3 )) ==> max(2,5) =
* fullMax = max(5,4) = 5
*
* 6th Iteration(a[6])
* semiMax = max (1, (1 + 5) ) ==> max(1,6) =
* fullMax = max(6,5) = 6
*
* 7rd Iteration(a[7])
* semiMax = max (-5, (-5 + 6 ) ) ==> max(-5,1) = 1
* fullMax = max(1,6) = 6
*
* 8th Iteration(a[8])
* semiMax = max (4, (4 + 1) ) ==> max(4,5) = 5
* fullMax = max(5,6) = 6
* **/