F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2

public class Fibonacci {
    // 递归方法
    public static int fibonacciRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }

    public static void main(String[] args) {
        int n = 10; // 示例：计算第10个斐波那契数
        System.out.println("Fibonacci number at position " + n + " is: " + fibonacciRecursive(n));
    }
}

public class Fibonacci {
    // 迭代方法
    public static int fibonacciIterative(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 10; // 示例：计算第10个斐波那契数
        System.out.println("Fibonacci number at position " + n + " is: " + fibonacciIterative(n));
    }
}

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    private static Map<Integer, Integer> cache = new HashMap<>();

    // 动态规划方法
    public static int fibonacciDP(int n) {
        if (n <= 1) {
            return n;
        }
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int result = fibonacciDP(n - 1) + fibonacciDP(n - 2);
        cache.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10; // 示例：计算第10个斐波那契数
        System.out.println("Fibonacci number at position " + n + " is: " + fibonacciDP(n));
    }
}

public class LCS {
    // 方法：计算两个字符串的最长公共子序列长度
    public static int longestCommonSubsequence(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1];

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }

    // 方法：构建最长公共子序列
    public static String buildLCS(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1];

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 回溯构建LCS字符串
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                lcs.append(X.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcs.reverse().toString();
    }

    public static void main(String[] args) {
        String X = "ABCBDAB";
        String Y = "BDCAB";
        
        int length = longestCommonSubsequence(X, Y);
        System.out.println("Length of LCS: " + length); // 输出：4
        
        String lcs = buildLCS(X, Y);
        System.out.println("LCS: " + lcs); // 输出：BCAB 或 BDAB
    }
}

public class Knapsack {
    // 方法：解决0/1背包问题
    public static int knapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];

        // 填充dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3}; // 物品的重量
        int[] values = {6, 10, 12}; // 物品的价值
        int W = 5; // 背包的容量

        int maxValue = knapsack(weights, values, W);
        System.out.println("Maximum value in the knapsack: " + maxValue); // 输出：22
    }
}

public class EditDistance {
    // 方法：计算两个字符串的编辑距离
    public static int levenshteinDistance(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化dp数组
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String str1 = "kitten";
        String str2 = "sitting";
        
        int distance = levenshteinDistance(str1, str2);
        System.out.println("Edit distance between '" + str1 + "' and '" + str2 + "': " + distance); // 输出：3
    }
}

public class MaxSubArraySum {
    // 方法：计算最大子数组和
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array cannot be null or empty");
        }

        int maxCurrent = nums[0];
        int maxGlobal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;
            }
        }

        return maxGlobal;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = maxSubArray(nums);
        System.out.println("Maximum subarray sum is: " + result); // 输出：6
    }
}

public class UniquePaths {
    // 方法：计算机器人从左上角到右下角的不同路径数
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // 初始化第一行和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // 填充dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        int m = 3; // 行数
        int n = 7; // 列数
        int result = uniquePaths(m, n);
        System.out.println("Number of unique paths: " + result); // 输出：28
    }
}

public class ClimbingStairs {
    // 方法：计算到达顶部的不同方法数
    public static int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1; // 起点
        dp[1] = 1; // 第一阶

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5; // 楼梯总阶数
        int result = climbStairs(n);
        System.out.println("Number of ways to climb " + n + " stairs: " + result); // 输出：8
    }
}

public class MinPathSum {
    // 方法：计算从左上角到右下角的最小路径和
    public static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        // 初始化第一行和第一列
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        // 填充dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        int result = minPathSum(grid);
        System.out.println("Minimum path sum: " + result); // 输出：7
    }
}

public class StockBuySell {
    // 方法：计算最大利润
    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0; // 无法进行交易
        }

        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price; // 更新最低价格
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice; // 更新最大利润
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        int result = maxProfit(prices);
        System.out.println("Maximum profit: " + result); // 输出：5
    }
}

public class HouseRobber {
    // 方法：计算最大抢劫金额
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // 没有房子可以抢劫
        }
        if (nums.length == 1) {
            return nums[0]; // 只有一个房子
        }

        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[n-1];
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        int result = rob(nums);
        System.out.println("Maximum amount: " + result); // 输出：12
    }
}

public class CoinChange {
    // 方法：计算最少硬币数量
    public static int coinChange(int[] coins, int amount) {
        if (amount < 0) return -1; // 无效金额
        int[] dp = new int[amount + 1];
        dp[0] = 0; // 组成金额0需要0个硬币

        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1; // 初始化为一个较大的值
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        int result = coinChange(coins, amount);
        System.out.println("Minimum coins needed: " + result); // 输出：3
    }
}

public class JumpGame {
    public boolean canJump(int[] nums) {
        // 初始化最远能跳到的位置为0
        int maxReach = 0;
        
        // 遍历数组中的每一个元素
        for (int i = 0; i < nums.length; i++) {
            // 如果当前位置已经超出了最远能跳到的位置，则无法继续前进
            if (i > maxReach) {
                return false;
            }
            // 更新最远能跳到的位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 如果最远能跳到的位置已经大于或等于数组的最后一个位置，返回true
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        
        // 如果循环结束后仍未能到达数组末尾，返回false
        return false;
    }

    public static void main(String[] args) {
        JumpGame game = new JumpGame();
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(game.canJump(nums)); // 输出: true
        
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println(game.canJump(nums2)); // 输出: false
    }
}

import java.util.List;

public class TriangleMinPathSum {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        // 获取三角形的高度
        int n = triangle.size();
        
        // dp数组用于存储到达每个位置的最小路径和
        int[] dp = new int[n];
        
        // 初始化dp数组为三角形最底层的值
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        
        // 从倒数第二层开始往上计算
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 状态转移方程：dp[j] = min(dp[j], dp[j + 1]) + triangle.get(i).get(j)
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        
        // 最终结果在dp[0]中
        return dp[0];
    }

    public static void main(String[] args) {
        TriangleMinPathSum solution = new TriangleMinPathSum();
        List<List<Integer>> triangle = List.of(
            List.of(2),
            List.of(3, 4),
            List.of(6, 5, 7),
            List.of(4, 1, 8, 3)
        );
        int result = solution.minimumTotal(triangle);
        System.out.println("Minimum path sum is: " + result); // 输出: 11
    }
}

dp[i] = !dp[i - k] for all k in range(1, i // 2 + 1)

public class StoneGame {
    public boolean stoneGame(int n) {
        // 创建一个布尔数组 dp，大小为 n+1
        boolean[] dp = new boolean[n + 1];
        
        // 初始化 dp 数组
        dp[0] = false; // 没有石子时，先手必败
        dp[1] = true;  // 只有一个石子时，先手必胜
        
        // 填充 dp 数组
        for (int i = 2; i <= n; i++) {
            dp[i] = false; // 默认先手必败
            for (int k = 1; k <= i / 2; k++) {
                if (!dp[i - k]) {
                    dp[i] = true; // 找到一个可以使对手必败的情况
                    break;
                }
            }
        }
        
        return dp[n];
    }

    public static void main(String[] args) {
        StoneGame game = new StoneGame();
        int n = 4;
        System.out.println("For " + n + " stones, first player wins: " + game.stoneGame(n)); // 输出: true
    }
}

import java.util.Stack;

public class MaximalRectangle {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        int[] heights = new int[matrix[0].length];
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // Update the height array
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            // Calculate the maximum area for this row's histogram
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        return maxArea;
    }

    public static void main(String[] args) {
        MaximalRectangle solution = new MaximalRectangle();
        char[][] matrix = {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
        };
        int result = solution.maximalRectangle(matrix);
        System.out.println("Maximum rectangle area is: " + result); // 输出: 6
    }
}

public class RegexMatcher {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]; // Star represents zero occurrence of the preceding element
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j]; // Star represents one or more occurrences
                    }
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        RegexMatcher matcher = new RegexMatcher();
        String s = "aab";
        String p = "c*a*b";
        System.out.println("Is match: " + matcher.isMatch(s, p)); // Should output true
    }
}

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        int maxLength = 1; // 初始化最大长度为1，因为每个元素自身可以作为一个子序列

        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1; // 每个元素自身至少可以构成长度为1的子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("The length of the longest increasing subsequence is: " + lis.lengthOfLIS(nums));
    }
}

The length of the longest increasing subsequence is: 4

public class MaxProductSubarray {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 初始化最大值、最小值和结果
        int max = nums[0], min = nums[0], result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int tempMax = max; // 临时变量保存当前的最大值
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(tempMax * nums[i], min * nums[i]), nums[i]);
            result = Math.max(result, max);
        }

        return result;
    }

    public static void main(String[] args) {
        MaxProductSubarray solution = new MaxProductSubarray();
        int[] nums = {2, 3, -2, 4};
        System.out.println("The maximum product of a subarray is: " + solution.maxProduct(nums));
    }
}

The maximum product of a subarray is: 6

public class MinJumps {
    public int minJumps(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1; // 如果数组为空，返回-1表示无法跳跃
        }

        int n = nums.length;
        if (n == 1) {
            return 0; // 如果数组只有一个元素，不需要跳跃
        }

        // jumps[i] 表示到达第 i 个位置所需的最小跳跃次数
        int[] jumps = new int[n];
        jumps[0] = 0; // 起始位置的跳跃次数为0

        for (int i = 1; i < n; i++) {
            jumps[i] = Integer.MAX_VALUE; // 初始化为最大值
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i && jumps[j] != Integer.MAX_VALUE) {
                    jumps[i] = Math.min(jumps[i], jumps[j] + 1);
                }
            }
        }

        return jumps[n - 1]; // 返回到达最后一个位置的最小跳跃次数
    }

    public static void main(String[] args) {
        MinJumps solution = new MinJumps();
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println("The minimum number of jumps to reach the end is: " + solution.minJumps(nums));
    }
}

The minimum number of jumps to reach the end is: 2

public class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 0;

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide; // 返回最大正方形的面积
    }

    public static void main(String[] args) {
        MaximalSquare solution = new MaximalSquare();
        char[][] matrix = {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
        };
        System.out.println("The area of the largest square containing only 1s is: " + solution.maximalSquare(matrix));
    }
}

{
    {'1', '0', '1', '0', '0'},
    {'1', '0', '1', '1', '1'},
    {'1', '1', '1', '1', '1'},
    {'1', '0', '0', '1', '0'}
}

The area of the largest square containing only 1s is: 4

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // 奇数长度的回文
            int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度的回文
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();
        String s = "babad";
        System.out.println("The longest palindromic substring is: " + solution.longestPalindrome(s));
    }
}

The longest palindromic substring is: "bab" or "aba"

public class MaxConsecutiveOnes {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int currentCount = 0;

        for (int num : nums) {
            if (num == 1) {
                currentCount++;
                maxCount = Math.max(maxCount, currentCount);
            } else {
                currentCount = 0;
            }
        }

        return maxCount;
    }

    public static void main(String[] args) {
        MaxConsecutiveOnes solution = new MaxConsecutiveOnes();
        int[] nums = {1, 1, 0, 1, 1, 1};
        System.out.println("The maximum number of consecutive 1s is: " + solution.findMaxConsecutiveOnes(nums));
    }
}

The maximum number of consecutive 1s is: 3

public class MaximumProductSubarray {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int max = nums[0], min = nums[0], result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
            result = Math.max(result, max);
        }

        return result;
    }

    public static void main(String[] args) {
        MaximumProductSubarray solution = new MaximumProductSubarray();
        int[] nums = {2, 3, -2, 4};
        System.out.println("The maximum product of a subarray is: " + solution.maxProduct(nums));
    }
}

The maximum product of a subarray is: 6

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        MaximumSubarray solution = new MaximumSubarray();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("The maximum sum of a subarray is: " + solution.maxSubArray(nums));
    }
}

The maximum sum of a subarray is: 6

public class MinDeletionsToPalindrome {
    public int minDeletionsToMakePalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        MinDeletionsToPalindrome solution = new MinDeletionsToPalindrome();
        String s = "abca";
        System.out.println("The minimum deletions to make the string a palindrome are: " + solution.minDeletionsToMakePalindrome(s));
    }
}

The minimum deletions to make the string a palindrome are: 1