基于Kadane算法修改：最多平方一个元素的最大子数组和求解

原Kadane算法仅跟踪未使用平方操作的子数组和，要解决“最多平方一个元素”的问题，需要同时维护两种状态的子数组和：

• maxEndingNoSquare：以当前元素结尾，且未使用过平方操作的最大子数组和
• maxEndingWithSquare：以当前元素结尾，且已使用过一次平方操作的最大子数组和

修改后的代码 #

public int maxSubarrayWithOneSquare(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    // 初始化第一个元素的两种状态
    int maxEndingNoSquare = nums[0];
    int maxEndingWithSquare = nums[0] * nums[0];
    int globalMax = Math.max(maxEndingNoSquare, maxEndingWithSquare);

    for (int i = 1; i < n; i++) {
        // 更新未使用平方的状态：和原Kadane逻辑一致
        int newNoSquare = Math.max(maxEndingNoSquare + nums[i], nums[i]);
        
        // 更新已使用平方的状态：覆盖三种合法子数组形成方式
        int newWithSquare = Math.max(
            Math.max(maxEndingNoSquare + nums[i] * nums[i],  // 之前未平方，现在平方当前元素
                     maxEndingWithSquare + nums[i]),         // 之前已平方，直接追加当前元素
            nums[i] * nums[i]                                // 单独平方当前元素作为子数组
        );
        
        // 更新状态变量
        maxEndingNoSquare = newNoSquare;
        maxEndingWithSquare = newWithSquare;
        
        // 更新全局最大值
        globalMax = Math.max(globalMax, Math.max(maxEndingNoSquare, maxEndingWithSquare));
    }
    return globalMax;
}

关键修改点说明 #

1. 新增双状态跟踪：不再仅维护单一的子数组和状态，拆分出“未平方”和“已平方一次”两种情况，覆盖所有合法的子数组可能性。
2. 状态转移逻辑扩展：
   • 未平方状态的更新和原Kadane算法完全一致，选择“延续前序子数组”或“从当前元素重新开始”。
   • 已平方状态的更新考虑三种合法来源，确保不会遗漏任何可能的最优子数组。
3. 全局最大值的全面性：每次遍历都对比两种状态的当前最大值，既保留了原Kadane算法的无平方最优解，也加入了平方一次后的最优解。

测试用例验证 #

• 测试用例1：输入{-1,-2,3,-2,3}，遍历到最后一个3时，maxEndingWithSquare计算为max(1+9,7+3)=10，与预期结果一致。
• 测试用例2：输入{-4,-4,-2,5,2,-1}，遍历到元素2时，maxEndingWithSquare为5²+2=27，与预期结果一致。

内容的提问来源于stack exchange，提问作者Dawson Smith