Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique used to solve optimization

problems by breaking them down into simpler sub-problems and solving each sub-
problem just once, storing the results for future use. This approach avoids redundant
calculations and significantly reduces the computation time for problems with
overlapping sub-problems and optimal substructure properties.

Key Concepts of Dynamic Programming:

1. Optimal Substructure: The optimal solu\tion to the problem can be constructed from optimal
solutions of its sub-problems.
2. Overlapping Sub-problems: The problem can be broken down into sub-problems that are
reused multiple times.

Types of Dynamic Programming Approaches:

1. Top-Down (Memoization): Recursively break down the problem and store the results of sub-
problems in a table (array, hashmap) to avoid recomputation.
2. Bottom-Up (Tabulation): Iteratively solve all sub-problems and store their results in a table,
building up the solution from the simplest sub-problems.

1. Fibonacci Sequence

#include <stdio.h>
int fibonacci(int n) {
int dp[n+1];
dp[0] = 0;
dp[1] = 1;

for (int i = 2; i <= n; i++) {

dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main() {
int n = 10; // Example
printf("Fibonacci number at position %d is %d\n", n,
fibonacci(n));
return 0;
}
2. Longest Increasing Subsequence

Given an array of integers, find the length of the longest increasing subsequence.

Example

Consider the array arr = [10, 22, 9, 33, 21, 50, 41, 60, 80].

The longest increasing subsequence is [10, 22, 33, 50, 60, 80], and its length is
6.

#include <stdio.h>
int lis(int arr[], int n) {
int lis[n];
for (int i = 0; i < n; i++) lis[i] = 1;

for (int i = 1; i < n; i++) {

for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}

int max = 0;
for (int i = 0; i < n; i++) {
if (max < lis[i]) {
max = lis[i];
}
}
return max;
}
int main() {
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d\n", lis(arr, n));
return 0;
}

3. Knapsack Problem

Given a set of items, each with a weight and a value, determine the number of each
item to include in a collection so that the total weight does not exceed a given limit
and the total value is as large as possible. Each item can either be taken or not taken
(hence the name 0/1).
Example: Consider a knapsack with a weight capacity of W = 50 and the following
items:

Item Weight Value

1 10 60
2 20 100
3 30 120

The goal is to maximize the value without exceeding the weight capacity.

#include <stdio.h>
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1];

for (int i = 0; i <= n; i++) {

for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-
1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val,
n));
return 0;
}

4. Coin Change Problem

Given a set of m coin denominations {c1, c2, ..., cm} and a target amount V, find
the minimum number of coins needed to make the amount V. If it is not possible to
make the amount with the given coin denominations, return -1.
Approach:

 Use dynamic programming to build a solution.

 Create an array dp where dp[i] represents the minimum number of coins needed to make
the amount i.
 Initialize dp[0] to 0 because no coins are needed to make the amount 0.
 Initialize all other entries of dp to a value greater than the maximum possible (e.g.,
INT_MAX).
 For each coin, update the dp array by checking if using the coin results in a smaller number
of coins than the current value.

#include <stdio.h>
#include <limits.h>
int minCoins(int coins[], int m, int V) {
int dp[V+1];
dp[0] = 0;

for (int i = 1; i <= V; i++) {

dp[i] = INT_MAX;
}

for (int i = 1; i <= V; i++) {

for (int j = 0; j < m; j++) {
if (coins[j] <= i) {
int sub_res = dp[i - coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < dp[i]) {
dp[i] = sub_res + 1;
}
}
}
}
return dp[V];
}
int main() {
int coins[] = {1, 2, 5};
int m = sizeof(coins)/sizeof(coins[0]);
int V = 11;
printf("Minimum coins required is %d\n", minCoins(coins, m, V));
return 0;
}

5. Edit Distance

Given two strings, str1 and str2, find the minimum number of operations required
to convert str1 into str2.
Example

Consider the strings str1 = "kitten" and str2 = "sitting".

The edit distance between them is 3, with the following operations:

1. Substitute 'k' with 's' (kitten -> sitten)

2. Substitute 'e' with 'i' (sitten -> sittin)
3. Insert 'g' at the end (sittin -> sitting)

#include <stdio.h>
#include <string.h>
int min(int x, int y, int z) {
return x < y ? (x < z ? x : z) : (y < z ? y : z);
}
int editDistance(char str1[], char str2[], int m, int n) {
int dp[m+1][n+1];

for (int i = 0; i <= m; i++) {

for (int j = 0; j <= n; j++) {
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-
1]);
}
}
return dp[m][n];
}
int main() {
char str1[] = "sunday";
char str2[] = "saturday";
printf("Edit Distance = %d\n", editDistance(str1, str2,
strlen(str1), strlen(str2)));
return 0;
}

5. Longest Common Subsequence

Given two sequences (strings), find the length of their longest common subsequence.
A subsequence is a sequence derived by deleting some or no elements of the sequence
without changing the order of the remaining elements.

Example

Consider the strings str1 = "ABCBDAB" and str2 = "BDCAB".

The longest common subsequence is "BCAB", and its length is 4.

#include <stdio.h>
#include <string.h>
int max(int a, int b) { return (a > b) ? a : b; }
int lcs(char* X, char* Y, int m, int n) {
int dp[m+1][n+1];

for (int i = 0; i <= m; i++) {

for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (X[i-1] == Y[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
int main() {
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}

7. 0/1 Knapsack Problem with Space Optimization

Given a set of items, each with a weight and a value, determine the number of each
item to include in a collection so that the total weight is less than or equal to a given
limit and the total value is as large as possible. Each item can either be included in the
collection or not (hence the name 0/1).

Problem Statement
Given:

 n items, each with a weight w[i] and a value v[i].

 A knapsack with a maximum capacity W.

Find the maximum value that can be achieved by selecting a subset of the items such
that their total weight does not exceed W.

Example

Consider the following items and knapsack capacity:

Items:

 Item 1: weight = 2, value = 3

 Item 2: weight = 3, value = 4
 Item 3: weight = 4, value = 5
 Item 4: weight = 5, value = 8

Knapsack capacity: W = 5

The maximum value that can be achieved is 8 by selecting item 4.

#include <stdio.h>
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n) {
int dp[W+1];
for (int i = 0; i <= W; i++) dp[i] = 0;

for (int i = 0; i < n; i++) {

for (int w = W; w >= wt[i]; w--) {
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
}
return dp[W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val,
n));
return 0;
}
8. Subset Sum Problem

Given a set of n integers and a target sum S, determine if there is a subset of the given
set with a sum equal to S.

Example

Consider the set arr = {3, 34, 4, 12, 5, 2} and target sum S = 9.

The subset {4, 5} sums to 9, so the answer is true.

#include <stdio.h>
#include <stdbool.h>
bool isSubsetSum(int set[], int n, int sum) {
bool dp[sum+1];
for (int i = 0; i <= sum; i++) dp[i] = false;

dp[0] = true;

for (int i = 0; i < n; i++) {

for (int j = sum; j >= set[i]; j--) {
if (dp[j - set[i]]) {
dp[j] = true;
}
}
}
return dp[sum];
}
int main() {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = sizeof(set)/sizeof(set[0]);
if (isSubsetSum(set, n, sum))
printf("Found a subset with given sum\n");
else
printf("No subset with given sum\n");
return 0;
}

9. Matrix Chain Multiplication

Given a sequence of matrices A1,A2,…,AnA1​ ,A2​ ,…,An​ where AiAi​ has

dimensions pi−1×pipi−1​ ×pi​ , the task is to find the most efficient way to multiply
these matrices together. The order in which the matrices are multiplied can
significantly affect the number of operations required.
Example

Consider the matrices with dimensions:

 A1A1​ : 10×3010×30
 A2A2​ : 30×530×5
 A3A3​ : 5×605×60

The optimal way to multiply these matrices together to minimize the number of scalar
multiplications can be different from simply multiplying them in the given order.

#include <stdio.h>
#include <limits.h>
int matrixChainOrder(int p[], int n) {
int dp[n][n];
for (int i = 1; i < n; i++) dp[i][i] = 0;

for (int L = 2; L < n; L++) {

for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
dp[i][j] = INT_MAX;
for (int k = i; k <= j - 1; k++) {
int q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
if (q < dp[i][j])
dp[i][j] = q;
}
}
}
return dp[1][n-1];
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d\n",
matrixChainOrder(arr, n));
return 0;
}

10. Minimum Cost Path

Given a grid (2D array) of size m x n where each cell contains a non-negative integer
representing the cost to traverse that cell, find the minimum cost path from the top-left
corner (cell [0][0]) to the bottom-right corner (cell [m-1][n-1]).

Example
Consider the following cost matrix:

1 3 1
1 5 1
4 2 1

The minimum cost path from the top-left corner to the bottom-right corner is 1 -> 3
-> 1 -> 1 -> 1, which has a total cost of 7.

#include <stdio.h>
#include <limits.h>
#define R 3
#define C 3
int min(int x, int y, int z) {
return x < y ? (x < z ? x : z) : (y < z ? y : z);
}
int minCost(int cost[R][C], int m, int n) {
int dp[R][C];
dp[0][0] = cost[0][0];

for (int i = 1; i <= m; i++)

dp[i][0] = dp[i-1][0] + cost[i][0];

for (int j = 1; j <= n; j++)

dp[0][j] = dp[0][j-1] + cost[0][j];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
dp[i][j] = cost[i][j] + min(dp[i-1][j-1], dp[i-1][j],
dp[i][j-1]);
}
}
return dp[m][n];
}
int main() {
int cost[R][C] = { {1, 2, 3},
{4, 8, 2},
{1, 5, 3} };
printf("Minimum cost to reach (2, 2) is %d\n", minCost(cost, 2,
2));
return 0;
}

11. Maximum Sum Subarray (Kadane's Algorithm)

Kadane's Algorithm is a popular and efficient method used to find the maximum sum
of a contiguous subarray within a one-dimensional array of numbers. This algorithm
runs in linear time, making it very efficient for this type of problem.

Problem Statement

Given an array of integers, find the contiguous subarray (containing at least one
number) which has the largest sum and return its sum.

Example

Consider the array:

css
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The contiguous subarray with the maximum sum is [4, -1, 2, 1], which has a sum
of 6.

Kadane's Algorithm

Kadane's Algorithm maintains a running maximum sum of the subarray ending at the
current position and updates the overall maximum sum found so far.

Steps:

Initialization:

1. Initialize two variables:

1. max_current to keep track of the maximum sum of the subarray ending
at the current position.
2. max_global to keep track of the maximum sum found so far.
2. Set both max_current and max_global to the first element of the array.

Iterate Through the Array:

1. For each element in the array (starting from the second element), update
max_current to be the maximum of the current element itself or the current
element plus max_current. This step decides whether to add the current
element to the existing subarray or to start a new subarray from the current
element.
2. Update max_global to be the maximum of max_global and max_current.

Result:

1. After iterating through the array, max_global will contain the maximum sum of
the contiguous subarray.

#include <stdio.h>
#include <limits.h>
int maxSubArraySum(int arr[], int size) {
int max_so_far = INT_MIN, max_ending_here = 0;

for (int i = 0; i < size; i++) {

max_ending_here = max_ending_here + arr[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Maximum contiguous sum is %d\n", maxSubArraySum(arr, n));
return 0;
}

12. Minimum Number of Coins for Change (Unbounded Knapsack

Variation)

The Minimum Number of Coins for Change problem is a variation of the classic
Unbounded Knapsack problem. In this problem, given a target amount and a set of
coin denominations, the goal is to find the minimum number of coins needed to make
the target amount.

Problem Statement

Given an integer amount representing the target amount of money and an array coins
representing the denominations of coins available, find the minimum number of coins
needed to make the amount. You can assume that there is an infinite supply of each
coin denomination.

Example

Consider the following example:

 amount = 11
 coins = [1, 2, 5]

To make the amount 11, we can use the following combinations:

 11 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, using 11 coins of
denomination 1.
 11 = 5 + 5 + 1, using 3 coins (2 of denomination 5 and 1 of denomination 1).
  11 = 5 + 2 + 2 + 2, using 4 coins (1 of denomination 5 and 3 of denomination 2).

The minimum number of coins needed is 3.

#include <stdio.h>
#include <limits.h>
int minCoins(int coins[], int m, int V) {
int dp[V+1];
for (int i = 0; i <= V; i++) dp[i] = INT_MAX;
dp[0] = 0;

for (int i = 1; i <= V; i++) {

for (int j = 0; j < m; j++) {
if (coins[j] <= i) {
int sub_res = dp[i - coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < dp[i])
dp[i] = sub_res + 1;
}
}
}
return dp[V];
}
int main() {
int coins[] = {1, 2, 3};
int m = sizeof(coins)/sizeof(coins[0]);
int V = 5;
printf("Minimum coins required is %d\n", minCoins(coins, m, V));
return 0;
}

13. Longest Palindromic Subsequence

A Longest Palindromic Subsequence (LPS) is a sequence of characters that reads the

same forwards and backwards. The problem of finding the Longest Palindromic
Subsequence in a given string is a classic problem in computer science and dynamic
programming.

Problem Statement

Given a string s, find the length of the Longest Palindromic Subsequence (LPS) in s.

Example

Consider the string s = "bbbab".

A possible Longest Palindromic Subsequence is "bbbb", which has a length of 4.

#include <stdio.h>
#include <string.h>
int max(int a, int b) { return (a > b) ? a : b; }
int lps(char* seq, int i, int j) {
if (i == j)
return 1;
if (seq[i] == seq[j] && i + 1 == j)
return 2;
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
int main() {
char seq[] = "KIIT UNIVERSITY";
int n = strlen(seq);
printf("The length of the LPS is %d\n", lps(seq, 0, n - 1));
return 0;
}

14. Egg Dropping Puzzle

Given nn eggs and a building with mm floors, determine the minimum

number of attempts needed to find the highest floor from which an egg
can be dropped without breaking. You are provided with an unlimited
number of eggs and can use them in any way you want.

#include <stdio.h>
#include <limits.h>
int max(int a, int b) { return (a > b) ? a : b; }
int eggDrop(int n, int k) {
int dp[n+1][k+1];
int res;
for (int i = 1; i <= n; i++) {
dp[i][1] = 1;
dp[i][0] = 0;
}

for (int j = 1; j <= k; j++)

dp[1][j] = j;

for (int i = 2; i <= n; i++) {

for (int j = 2; j <= k; j++) {
 dp[i][j] = INT_MAX;
for (int x = 1; x <= j; x++) {
res = 1 + max(dp[i-1][x-1], dp[i][j-x]);
if (res < dp[i][j])
dp[i][j] = res;
}
}
}
return dp[n][k];
}
int main() {
int n = 2, k = 10;
printf("Minimum number of trials in worst case with %d eggs
and %d floors is %d\n", n, k, eggDrop(n, k));
return 0;
}

15. Maximum Size Square Sub-matrix with All 1s

Given a binary matrix where each cell contains either a 0 or a 1, the

goal is to find the largest square sub-matrix containing only 1s and
return its side length.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define R 6
#define C 5
int min(int a, int b, int c) {
int m = a;
if (m > b) m = b;
if (m > c) m = c;
return m;
}
void printMaxSubSquare(int M[R][C]) {
int i, j;
int S[R][C];
int max_of_s, max_i, max_j;

for (i = 0; i < R; i++)

S[i][0] = M[i][0];

for (j = 0; j < C; j++)

S[0][j] = M[0][j];
 for (i = 1; i < R; i++) {
for (j = 1; j < C; j++) {
if (M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}

max_of_s = S[0][0]; max_i = 0; max_j = 0;

for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) {
if (max_of_s < S[i][j]) {
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf("Maximum size sub-matrix is: \n");

for (i = max_i; i > max_i - max_of_s; i--) {
for (j = max_j; j > max_j - max_of_s; j--) {
printf("%d ", M[i][j]);
}
printf("\n");
}
}
int main() {
int M[R][C] = { {0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0} };
printMaxSubSquare(M);
return 0;
}

16. Longest Palindromic Substring

Given a string, the goal is to find the longest substring that is a

palindrome.
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
void printSubStr(char* str, int low, int high) {
for (int i = low; i <= high; ++i)
printf("%c", str[i]);
}
int longestPalSubstr(char* str) {
int n = strlen(str);
bool table[n][n];
memset(table, 0, sizeof(table));

int maxLength = 1;
for (int i = 0; i < n; ++i)
table[i][i] = true;

int start = 0;
for (int i = 0; i < n - 1; ++i) {
if (str[i] == str[i + 1]) {
table[i][i + 1] = true;
start = i;
maxLength = 2;
}
}

for (int k = 3; k <= n; ++k) {

for (int i = 0; i < n - k + 1; ++i) {
int j = i + k - 1;
if (table[i][j - 1] && str[i] == str[j]) {
table[i][j] = true;
if (k > maxLength) {
start = i;
maxLength = k;
}
}
}
}

printf("Longest palindrome substring is: ");

printSubStr(str, start, start + maxLength - 1);

return maxLength;
}
int main() {
char str[] = "kiitiit";
printf("\nLength is: %d\n", longestPalSubstr(str));
return 0;
}

17. Count of Subsets with a Given Sum.

Given an array arr[] of integers and a target sum target, find the
number of subsets of arr[] whose elements sum up to target.

#include <stdio.h>
int countSubsets(int arr[], int n, int sum) {
int dp[n+1][sum+1];

for (int i = 0; i <= n; i++)

dp[i][0] = 1;

for (int i = 1; i <= sum; i++)

dp[0][i] = 0;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= sum; j++) {
if (arr[i-1] <= j)
dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i-1]];
else
dp[i][j] = dp[i-1][j];
}
}

return dp[n][sum];
}
int main() {
int arr[] = {2, 3, 5, 6, 8, 10};
int sum = 10;
int n = sizeof(arr)/sizeof(arr[0]);
printf("Count of subsets with given sum is %d\n",
countSubsets(arr, n, sum));
return 0;
}

18. Boolean Parenthesization Problem

Given a boolean expression expr[] consisting of boolean variables
(true and false) and boolean operators (&, |, and ^), and a desired
boolean result result, find the number of ways to parenthesize the
expression such that it evaluates to the desired result.

#include <stdio.h>
#include <string.h>
int countWays(int N, char* S) {
int dpTrue[N][N], dpFalse[N][N];
memset(dpTrue, 0, sizeof(dpTrue));
memset(dpFalse, 0, sizeof(dpFalse));

for (int i = 0; i < N; i += 2) {

dpTrue[i][i] = S[i] == 'T' ? 1 : 0;
dpFalse[i][i] = S[i] == 'F' ? 1 : 0;
}

for (int length = 3; length <= N; length += 2) {

for (int i = 0; i <= N - length; i += 2) {
int j = i + length - 1;
dpTrue[i][j] = dpFalse[i][j] = 0;

for (int k = i + 1; k < j; k += 2) {

int leftT = dpTrue[i][k-1];
int leftF = dpFalse[i][k-1];
int rightT = dpTrue[k+1][j];
int rightF = dpFalse[k+1][j];

if (S[k] == '&') {
dpTrue[i][j] += leftT * rightT;
dpFalse[i][j] += leftT * rightF + leftF * rightT
+ leftF * rightF;
}
else if (S[k] == '|') {
dpFalse[i][j] += leftF * rightF;
dpTrue[i][j] += leftT * rightT + leftT * rightF +
leftF * rightT;
}
else if (S[k] == '^') {
dpTrue[i][j] += leftT * rightF + leftF * rightT;
dpFalse[i][j] += leftT * rightT + leftF * rightF;
}
}
}
 }

return dpTrue[0][N-1];
}
int main() {
char symbols[] = "T|F&T^T";
int N = strlen(symbols);
printf("Number of ways to parenthesize the expression to get true
is %d\n", countWays(N, symbols));
return 0;
}

19. Rod Cutting Problem

Given a rod of length nn and a list of prices pipi​ for rods of

length ii (where ii ranges from 1 to nn), the goal is to determine
the maximum revenue that can be obtained by cutting and selling the
rod into smaller pieces.

#include <stdio.h>
int max(int a, int b) { return (a > b) ? a : b; }
int cutRod(int price[], int n) {
int dp[n+1];
dp[0] = 0;

for (int i = 1; i <= n; i++) {

int max_val = -1;
for (int j = 0; j < i; j++)
max_val = max(max_val, price[j] + dp[i-j-1]);
dp[i] = max_val;
}
return dp[n];
}
int main() {
int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum Obtainable Value is %d\n", cutRod(arr, size));
return 0;
}

20. Largest Sum Contiguous Subarray (Modified Kadane's

Algorithm for Handling All Negative Values)
The Largest Sum Contiguous Subarray problem, often solved using Kadane's
Algorithm, involves finding the maximum sum of a contiguous subarray within an
array of integers.

However, when all the numbers in the array are negative, Kadane's algorithm may
return 0 (indicating an empty subarray), which may not be the desired behavior. To
handle this scenario, we can modify Kadane's Algorithm to return the maximum
element in the array when all the elements are negative.

Problem Statement

Given an array of integers, find the contiguous subarray with the largest sum.

Modified Kadane's Algorithm

Here's how we can modify Kadane's Algorithm to handle the case when all elements
are negative:

Initialization:

1. Initialize two variables: max_so_far and max_ending_here to store the

maximum sum found so far and the maximum sum ending at the current position,
respectively.
2. Initialize max_elem to store the maximum element in the array.

Traverse the Array:

1. For each element in the array:

 Update max_ending_here as the maximum of the current element and

the sum of the current element and max_ending_here.
 Update max_so_far as the maximum of max_so_far and
max_ending_here.
 Update max_elem as the maximum of max_elem and the current
element.

Result:

1. If max_so_far is greater than 0, return max_so_far.

2. If max_so_far is 0 (indicating that all elements are negative), return max_elem.

#include <stdio.h>
#include <limits.h>
int maxSubArraySum(int arr[], int size) {
int max_so_far = INT_MIN, max_ending_here = 0;

for (int i = 0; i < size; i++) {

max_ending_here = max_ending_here + arr[i];
if (max_ending_here > max_so_far)
 max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}

if (max_so_far == INT_MIN) {
max_so_far = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max_so_far)
max_so_far = arr[i];
}
}

return max_so_far;
}
int main() {
int arr[] = {-2, -3, -1, -5, -6};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Maximum contiguous sum is %d\n", maxSubArraySum(arr, n));
return 0;
}